Главная > Математика > Введение в теорию чисел. Алгоритм RSA
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

§ 3.8. Единственность разложения

Пришло время доказать, что представление натурального числа в виде, указанном в § 3.1, единственно. Мы докажем единственность от противного, воспользовавшись фундаментальным свойством простых чисел.

Предположим, напротив, что существуют натуральные числа, большие 2, допускающие больше одного разложения. Пусть

наименьшее натуральное число, у которого есть по крайней мере два различных разложения. Пусть

где простые, а натуральные числа. Кроме того, мы предполагаем, что эти два разложения различны. Заметим, что такое может произойти по двум причинам. Во-первых, в одном из разложений могут присутствовать простые множители, которых нет в другом. Во-вторых, даже если набор простых множителей в обоих случаях одинаков, их кратности могут быть различными. К счастью, неважно, какая именно из этих возможностей реализуется в разложении (8.1).

Исследуя левое разложение, мы заключаем, что делится на Но Многократное применение фундаментального свойства простых чисел показывает, что один из сомножителей в должен делиться на а значит одно из чисел 9, должно делиться Но простое число делится на другое простое, только если они равны. Значит для некоторого

Поэтому в правом разложении числа можно заменить на

Теперь на можно сократить, поскольку оно входит в оба разложения в положительной степени. В результате получим

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

выбрали в качестве наименьшее положительное число с двумя различными разложениями, а Раз полученные разложения совпадают, то а кроме того Далее,

и кратности каждого простого числа в обоих разложениях тоже равны,

Однако из этих равенств вытекает, что разложения в (8.1) также одинаковы, и мы пришли к противоречию. Значит, представление натурального числа в виде, указанном в теореме из § 3.1, единственно.

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

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

Если посмотреть на историю математики последнего столетия, то в ней найдется огромное количество примеров «числовых систем», элементы которых допускают разложение на неприводимые. Такое разложение, как правило, не единственно. Самый знаменитый контрпример связан с великой

теоремой Ферма. Так называют сформулированное Ферма утверждение о том, что если

для некоторой степени то На своем экземпляре диофантовой «Арифметики» Ферма пометил, что у него есть поистине замечательное доказательство этого факта, однако поля слишком узки, чтобы его привести.

Очевидная стратегия доказательства основана на том, чтобы полностью разложить разность Для этого необходимо ввести комплексные числа; тогда

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

Предполагается, что «доказательство» Ферма содержало аналогичную ошибку. Ферма мог попасться в ловушку, полагая, что разложение на множители в множестве комплексных чисел, с которым он работал, единственно. Было бы неудивительно, если бы Ферма пал жертвой такой ошибки. Как мы уже говорили в § 3.1, только Гаусс сформулировал утверждение о единственности разложения на множители в том явном виде, которым мы пользуемся и по сей день. Даже после выхода «Исследований» Гаусса, Куммер (Kummer) предложил доказательство теоремы Ферма, похожее на изложенное выше, не понимая, в чем заключается проблема, пока один из коллег не указал ему на ошибку. Не желая оставаться побежденным, Куммер разработал метод, позволяющий обходить неединственность разложения на множители. В результате он

смог доказать великую теорему Ферма для большого круга новых простых

Великая теорема Ферма была в конце концов доказана Уайлсом в 1995 г. Он следовал путем, предложенным лишь в последние 10 лет, предшествовавшие его работе. Этот путь основан на теории эллиптических кривых, в которых Уайлс является экспертом. Более раннюю историю теоремы Ферма можно изучить по книге [15] ([Д.12]). Хорошее элементарное введение в идеи, лежащие в основе доказательства Уайлса, можно найти в [20].

Упражнения

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

<< Предыдущий параграф Следующий параграф >>
Оглавление