February 5th, 2013

moose, transparent

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

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

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

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

полезно в хозяйстве: 48-е простое число Мерсенна

Оказывается, на днях нашли новое простое число Мерсенна, оно же по совместительству теперь наибольшее известное простое число: 257,885,161-1.
ORLANDO, Florida -- On January 25th at 23:30:26 UTC, the largest known prime number, 257,885,161-1, was discovered on Great Internet Mersenne Prime Search (GIMPS) volunteer Curtis Cooper's computer.

The new prime number, 2 multiplied by itself 57,885,161 times, less one, has 17,425,170 digits.

With 360,000 CPUs peaking at 150 trillion calculations per second, 17th-year GIMPS is the longest continuously-running global "grassroots supercomputing"[1] project in Internet history.

Если вам не терпится посмотреть на виновника торжества, то вот он (осторожно, большая страница).

Ура нам, людям - какое великолепное достижение человеческого духа! И вообще, если подумать, что за мастерское создание - человек! Как благороден разумом! Как беспределен в своих способностях, обличьях и движениях! Как точен и чудесен в действии! Как он похож на ангела глубоким постижением! Как он похож на некоего бога! Краса вселенной! Венец всего живущего!
moose, transparent

объяснить

Троллейбусы, ходившие по Мюнхену в те годы, когда там работал крупный физик-теоретик Арнольд Зоммерфельд (1868 — 1954), охлаждались летом двумя маленькими вентиляторами без моторов, вставленными в два отверстия в потолке. На ходу под напором набегающего воздуха вентиляторы начинали вращаться. Один студент заметил, что, хотя направление вращения каждого вентилятора было совершенно случайным, он мог вращаться как по часовой стрелке, так и против нее, но два вентилятора в одном троллейбусе почти всегда вращались в противоположных направлениях. С вопросом "Почему это так?" студент обратился к Зоммерфельду.

— Это легко объяснить, — сказал теоретик. — Воздух сначала попадает на передний вентилятор и придает ему случайное направление вращения. Когда троллейбус движется, завихрения воздуха, созданные первым вентилятором, распространяются вдоль потолка назад, доходят до второго вентилятора и заставляют его вращаться в том же направлении.

— Но, профессор, — запротестовал студент, — дело как раз в том, что вентиляторы почти всегда вращаются в разных направлениях!

— Ага, — сказал Зоммерфельд, — прекрасно. Но это еще легче объяснить!

(источник по-русски. Я это прочитал по-английски процитированным из книги Absolute Zero Gravity, которая кажется чем-то вроде аналога "Физики продолжают шутить")