Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Category:

красивое доказательство

(эта запись может быть интересна математикам и сочувствующим)

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

Теорема ван-дер-Вардена говорит следующее. Предположим, мы раскрасили все натуральные числа {1,2,3...} в конечное число цветов. Тогда можно найти сколь угодно длинные арифметические прогрессии одного цвета. Или подробнее: для любого K существуют такие a, d, что числа a, a+d, a+2d, ... a+(K-1)d все одного цвета в данной раскраске.

Теперь предположим, что нам дали какой-то конечный список простых чисел P = {p_1,..., p_n}. Моя цель - доказать, что есть еще какое-то простое число p, которого нет в этом списке. Это докажет, что простых бесконечное число.

Раскрасим все натуральные числа в 2^n (2 в степени n) цветов следующим образом. Цвет числа X - это набор из n нулей или единиц, где на i-м месте стоит четность того порядка, с которым простое число p_i входит в множители X. Например, если список простых начинается {2,3,5,7,11...}, и X = 90 = 2^1 * 3^2 * 5^1, то цвет X будет (1,0,1,0,0....) потому что 2 и 5 входят 1 раз (нечетное число => 1), а 3 входит 2 раза (четное число => 0), а все остальные простые 0 раз. Всего цветов столько же, сколько разных векторов из нулей и единиц длиной n, т.е. 2^n, конечное число. Значит, мы можем применить теорему ван-дер-Вардена, и для любого K, который я дам (пока что я оставляю за собой право его фиксировать), мне гарантирована арифметическая прогрессия a, a+d, a+2d... длиной K, в которой у всех членов одинаковая ЧЕТНОСТЬ порядков всех p_i.

Моя цель теперь - доказать, что я смогу гарантировать, что у первых двух членов прогрессии, a и a+d, одинаковы не только ЧЕТНОСТЬ порядков, но и САМИ порядки, т.е. каждый p_i входит в них в виде множителя одинаковое число раз. Если я это докажу, то теорема доказана - почему? Потому что любое число можно разбить на простые множители. a и a+d разные числа, поэтому их разбивка на простые множители должна как-то различаться. Но если для всех p_i она не различается, то должны быть ЕЩЕ какие-то простые числа кроме p_i. Другими словами можно сказать так: если поделить a и a+d на все простые степени всех p_i, которые в них входят, то раз мы делим на то же самое, должно остаться два РАЗНЫХ числа, одно больше другого; любой простой множитель большего из чисел будет каким-то новым простым, которого нет среди p_i.

Теперь я беру какое-нибудь p_i и хочу доказать, что его порядок в a и a+d одинаковый; для этого я обозначу его порядок в a и его порядок в d через a' и d':

a = p_i^a' * L
d = p_i^d' * M

где L и M не деляется на p_i. Какой в таком случае будет порядок p_i суммы? Легко видеть, что если a' и d' разные числа, то порядок суммы будет меньшим из них; например, если a' меньшее, то p_i^a' можно вынести за скобки, а в скобках останется L + p_i^(d'-a')M, и эта сумма не делится на p_i. Если же порядки a' и d' одинаковые, то не гарантировано, что порядок суммы будет такой же, потому что может случайно получится, что L+M в скобках делится на p_i и добавляет к порядку суммы.

Я хочу гарантировать, что a' < d', т.е. порядок p_i в a, начала прогрессии, меньше порядка p_i в d, ее периода. Тогда в соответствии с вышеказанным порядок p_i в сумме a+d тоже будет a', и будет равенство порядков при a и a+d для всех p_i, что мне и нужно. Как я это гарантирую?

Предположим сначала, что a' > d'. Тогда порядок p_i в сумме a+d будет d'. Мне известно, что a и a+d одного цвета, т.е. ЧЕТНОСТЬ их порядков a' и d' одинаковая, и следовательно они отличаются минимум на 2. Если я возьму достаточно большую длину прогрессии K > p_i, то мне гарантировано также, что a+p_i*d тоже того же цвета, то есть порядок p_i той же четности, что a' и d'. Но это число - сумма чисел с порядками a' и d'+1, где d'+1 меньший, поэтому его порядок равен d'+1, и его четность отличается от d'. Это противоречие.

Осталось разобрать только случай a' = d'. Тогда я рассмотрю числа a (с порядком a') и
a + jd = p_i^a'(L + jM), где j я еще не зафиксировал, но оно меньше длины прогрессии K (которую я еще не выбрал). Порядок a+jd равен a' плюс то, сколько раз p_i входит в сумму L+jM. Поскольку L и M взаимно простые с p_i, я могу (вычисляя по модулю p_i^2) подобрать такое j < p_i^2, чтобы L+jM делилось на p_i, но не на p_i^2, и таким образом добавляла ровно 1 к порядку суммы, и меняла его четность. Это опять противоречие к гарантии, которую дает теорема ван-дер-Вардена.

Для того, чтобы убрать возможность a' > d', мне достаточно было взять K > p_i; для того, чтобы убрать возможность a' = d', мне достаточно было взять K > p_i^2. Значит, выбрав изначально K, большее чем квадрат наибольшего из p_i, я смогу гарантировать a' < d' для всех p_i, и это приведет меня к новому простому числу, что и требовалось доказать.
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.
  • 38 comments