?

Log in

основная теорема арифметики: доказательства по индукции - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

основная теорема арифметики: доказательства по индукции [фев. 5, 2013|12:08 am]
Anatoly Vorobey
[Tags|]

Основная теорема арифметики гласит, что любое натуральное число можно разложить на простые множители, и что это разложение единственно: любое другое разложение того же числа состоит ровно из тех же простых множителей, разве что поставленных в другом порядке.

Я писал недавно о том, почему эта теорема кажется тривиальной и очевидной, и почему этот взгляд ошибочен. Теперь напишу о том, как доказывают эту теорему. Эта запись требует некоторых математических знаний - например, я не буду объяснять, что такое доказательство по индукции.

У ОТА (Основной Теоремы Арифметики) есть две части: существование разложения на простые множители, и его единственность. Существование доказать тривиально по индукции, и тут проблем или вариантов нет. Предположим, что мы уже доказали существование для всех чисел меньше n. Если n простое, то оно само себе разложение, доказывать нечего. Иначе n = a*b, где a и b какие-то числа меньше его. По предположению индукции у каждого из них есть разложение; соединяя эти разложения вместе, получаем разложение для n.

Единственность - это нетривиальная часть ОТА. Нам нужно доказать, что если n = p1*p2*...*pk = q1*q2*...*qs - два разложения числа n, то числа p должны быть на самом деле равны числам q, разве что расположены в другом порядке. Для начала отметим, что достаточно доказать, что не может быть двух разложений, в которых ни одно p не равно ни одному q, т.е. у разложений нет общих простых множителей. Этого случая достаточно, потому что если у двух разных разложений есть общие множители, на них всегда можно поделить, и убрать их с обеих сторон, пока не останутся два разных разложения числа поменьше без общих множителей, а такого (как мы докажем) не может быть.

Итак, предположим, что ни одно p не равно ни одному q. На этом месте доказательства ОТА делятся на две группы: те, которые доказывают с помощью леммы Евклида, и те, которые доказывают напрямую по индукции.

Лемма Евклида гласит следующее: если простое число p делит произведение a*b (p|a*b), то p делит отдельно a или b (или оба): p|a или p|b. Эта лемма была известна Евклиду и появляется именно в таком виде в 7-й книге его Начал.

Предположим, мы доказали лемму Евклида; единственность разложение в ОТА следует из нее немедленно следующим образом. p1 делит все число n = q1*q2*...*qs, значит (применяя лемму Евклида много раз), оно должно делить какое-то qi. Поскольку мы предполагаем, что p1 не равно ни одному qi, и они разные простые числа, это невозможно. Так что главная работа в этом подходе - доказать лемму Евклида.

Почти во всех учебниках теории чисел, алгебры итд. ОТА доказывают именно так, через лемму Евклида. Но есть и другой подход, напрямую по индукции, который приводится в некоторых учебниках теории чисел. Полагаю, что он не очень популярен, потому что подход через лемму Евклида обобщается до гораздо более широкого класса структур: колец главных идеалов, в которых док-во по индукции в общем случае невозможно. Таким образом, док-во по индукции слишком сильно завязано на свойства натуральных чисел и не раскрывает "настоящей" причины, по которой единственность ОТА верна - так, мне кажется, думают многие математики.

Тем не менее в доказательствах по индукции есть своя прелесть - главное их преимущество в том, что они намного короче и проще обычного доказательства через лемму Евклида. В этой записи я опишу доказательства по индукции, а подход через лемму Евклида разберу отдельно позже.

Доказательств по индукции я знаю два разных, хоть они довольно похожи друг на друга.

1. Сначала опишу более элегантное, на мой взгляд. Это доказательство принадлежит Цермело, он опубликовал его в 1934 году, но упомянул тогда же, что нашел его еще примерно в 1912-м.

Предположим, мы доказали единственность для всех чисел, меньших n, и теперь доказываем для n. Мы можем предположить, что n непростое, иначе все тривиально. Пусть p - наименьший делитель n из всех делителей n, больших 1; очевидно, что p обязан быть простым делителем, иначе были бы делители еще меньше.

Мы хотим доказать следующее: в любом разложении n на простые множители встречается p. Если мы это докажем, то работа закончена - выше мы увидели, что достаточно показать, что нет разных разложений без общих множителей, а если p всегда присутствует, то он всегда общий множитель, так что таких разных не может быть. Этот же аргумент в развернутом виде: возьмем любые два разложения, они оба включают p, удалим его и получим два разложения числа n/p, согласно индуктивному предположению они должны быть одинаковыми, значит, и исходные два одинаковы.

Пусть n = q*q1*...*qs - произвольное разложение n, в котором множитель q отличается от p. Мы хотим доказать, что несмотря на это, p все равно найдется где-то среди других множителей q1...qs. Поскольку p минимальный делитель, q > p, так что посмотрим на число n - p*n/q. Оно меньше n и потому имеет единственное разложение; поскольку p делит это число, p должно участвовать в этом разложении. Однако это число равно также (q-p)*q1*...*qs. p не делит q-p, так что он обязан участвовать в разложении среди
q1*...*qs, что и требовалось доказать.

2. Теперь второе доказательство по индукции.

Предположим, n = p1*p2*...*pk = q1*q2*...*qs, и у разложений нет общих элементов. Мы можем предположить, что в каждом разложении есть хотя бы два множителя - иначе все тривиально - и пусть p1, q1 будут минимальными множителями в каждом разложении. Тогда p12 ≤ n, и то же верно насчет q1; поскольку они разные, одно из неравенств должно быть строгим, и следовательно p1*q1 < n. Рассмотрим число X = n - p1*q1; согласно индуктивному предположению у него есть единственное разложение. Поскольку и p1 и q1 делят n и делят p1*q1, каждое из них делит X и поэтому встречается в его единственном разложении. Единственность разложения X поэтому дает нам право записать X = p1*q1*Y, и соответственно n = p1*q1(1+Y). Но теперь, если мы посмотрим на n/p1, у которого тоже обязано быть единственное разложение, оно с одной стороны должно быть p2*...*pk, а с другой включать в себя q1, потому что n/p1 = q1(1+Y). Это противоречие, потому что q1 не встречается среди p2*...*pk.
СсылкаОтветить

Comments:
[User Picture]From: certus
2013-02-04 10:30 pm
Доказательство Цермело мне понравилось.

Мне ещё вот что показалось любопытным: у леммы Евклида ведь тоже есть несколько доказательств. Я правильно понимаю, что Евклид доказывал её, опираясь на алгоритм Евклида, а про соотношение Безу он не знал? А меж тем, только доказательство через соотношение Безу обобщается на кольца главных идеалов — сам Евклид дальше своих колец бы не уехал ;)
(Ответить) (Thread)
[User Picture]From: avva
2013-02-05 12:57 pm
Я до сих пор пытаюсь разобраться, как именно Евклид доказывает лемму Евклида, и строго ли это доказательство. Может, напишу об этом отдельно. Это сложно понять, потому что под a/b = c/d он понимает что-то довольно сложное и имеющее нетривиальную структуру, но это описывается несколько туманным языком (ad = bc это у него следствие данного равенства, а не определение).

Кажется, он опирается на существование НОД, но не его выражение в виде линейной комбинации (в этом уверен).

Но если в общих чертах, то его доказательство опирается на следующую теорему (понять строгое док-во этой теоремы у него - в этом сложность):

ТЕОРЕМА. Пусть a/b дробь с минимальным представлением в том смысле, что для любой c/d так, что a/b = c/d, b <= d. Пусть a/b = c/d. Тогда a делит c, и b делит d, с одинаковым частным.

СЛЕДСТВИЕ. Пусть c,d взаимно простые. Тогда c/d есть минимальное представление в смысле, определенном выше. Доказательство: пусть a/b минимальная дробь из всех равных c/d. Согласно ТЕОРЕМЕ ax=c, bx=d, то есть x|c,d и поскольку c,d взаимно простые, x=1.

ЛЕММА ЕВКЛИДА. Пусть p = ab, x = ab/p. Тогда p/a = b/x. Если p не делит a, то p,a взаимно простые; применяя СЛЕДСТВИЕ и ТЕОРЕМУ, мы заключаем p|b.


Edited at 2013-02-05 19:56 (UTC)
(Ответить) (Parent) (Thread)
[User Picture]From: os80
2013-02-05 03:52 am
Анатолий, насколько я знаю, название Евклидовой книжки по-русски звучит как "Начала". Не то, чтобы сильно принципиально, однако есть такая культурная особенность.
(Ответить) (Thread)
[User Picture]From: avva
2013-02-05 09:05 am
ага, спасибо.
(Ответить) (Parent) (Thread)
From: asox
2013-02-05 11:11 am
Для начала отметим, что достаточно доказать, что не может быть двух разложений, в которых ни одно p не равно ни одному q, т.е. у разложений нет общих простых множителей.

Что-то странное предложение. Звучит как "не существует двух разложений, для которых все простые соммножители отличаются".
Сформулировано очень "неудобно".

Upd:
Даже лучше "не существует двух разложений, не имеющих хотя бы одного общего члена".

Более того, данное утверждение, фактически является почти полной формулировкой теоремы, а доказывается логически эквивалентная (но не совсем равная конструкция - для некоторого p в заданном разложении P всегда найдётся равное ему q из разложения Q.

Edited at 2013-02-05 11:17 (UTC)
(Ответить) (Thread)
[User Picture]From: falcao
2013-02-06 12:49 am

ab делится на p

Знакомо ли Вам доказательство "леммы Евклида" не через свойства НОД, и не через разложение единицы по двум взаимно простым числам, а через минимальный контрпример? Я такое рассуждение когда-то сочинил сам, но оно вообще-то довольно известное.

Кстати, труд Евклида в русскоязычной литературе словом "Элементы" тоже называют, хотя "Начала" -- более распространённый перевод.
(Ответить) (Thread)