![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
красивое доказательство
Dec. 11th, 2017 12:59 pm(эта запись может быть интересна математикам и сочувствующим)
Прочитал красивое и на удивление несложное доказательство теоремы о том, что есть бесконечно много простых чисел. Доказательств пользуется только одним продвинутым результатом: теоремой ван-дер-Вардена об арифметических прогрессиях, и пользуется ей довольно остроумно. Попробую пересказать тут.
Теорема ван-дер-Вардена говорит следующее. Предположим, мы раскрасили все натуральные числа {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, и это приведет меня к новому простому числу, что и требовалось доказать.
Прочитал красивое и на удивление несложное доказательство теоремы о том, что есть бесконечно много простых чисел. Доказательств пользуется только одним продвинутым результатом: теоремой ван-дер-Вардена об арифметических прогрессиях, и пользуется ей довольно остроумно. Попробую пересказать тут.
Теорема ван-дер-Вардена говорит следующее. Предположим, мы раскрасили все натуральные числа {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, и это приведет меня к новому простому числу, что и требовалось доказать.
