Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Category:

основная теорема арифметики: доказательства по индукции

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

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

У ОТА (Основной Теоремы Арифметики) есть две части: существование разложения на простые множители, и его единственность. Существование доказать тривиально по индукции, и тут проблем или вариантов нет. Предположим, что мы уже доказали существование для всех чисел меньше 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.
Tags: математика
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 6 comments