Математика. Настоящий учебник посвящен системе Mathematica прикладному пакету компьютерной алгебры, при помощи которого можно решать любые задачи, в которых в той или иной форме встречается математика
 Скачать 4.43 Mb.
|
|
Какие из них встречаются реже всего и почему? Вот еще одна классическая задача. Простые числа p и p + 2, разность которых равна 2, называются близнецами. 1.9. Найдите первые 1000 пар близнецов. Как меняется отношение коли- чества близнецов ≤ n к общему количеству простых чисел ≤ n? Ответ. Например, при помощи следующей конструкции: Select[Table[ {Prime[i],Prime[i]+2},{i,1,n}],PrimeQ[#[[2]]]&] Варварское, но верное решение состоит теперь в том, чтобы взять такое n, для которого этот список заведомо содержит больше 100 пар, например, n = 1000, и выбрать из него первые 100 посредством Take[list,100]. За исключением случая 3, 5, 7 числа вида p, p + 2, p + 4 не могут быть все три простыми (кстати, почему?) — но вот числа p, p + 2, p + 6 и p, p + 4, p + 6 могут. Еще интереснее искать четверки простых чисел p, p + 2, p + 6, p + 8. Первая такая четверка — это 5, 7, 11, 13, следующая — 11, 13, 17, 19. 1.10. Найдите первые 100 четверок. Есть ли среди них еще хотя бы одна такая, для которой последние цифры не есть 1, 3, 7, 9? Ответ. Перечислим лишь те четверки, которые меньше 10000. Кроме двух уже упомянутых, их еще всего 10 штук: 101 103 107 109 191 193 197 199 821 823 827 829 1481 1483 1487 1489 1871 1873 1877 1879 2081 2083 2087 2089 3251 3253 3257 3259 3461 3463 3467 3469 5651 5653 5657 5659 9431 9433 9437 9439 1.11. Убедитесь, что четверки встречаются очень часто. Указание. Искать большие четверки лучше, конечно, не посредством Se- lect, а организуя цикл начиная с некоторого места. Ответ. Набрав что-нибудь в духе Timing[Block[ {i=1000000000000000000001},While[ Not[PrimeQ[i]&&PrimeQ[i+2]&&PrimeQ[i+6]&&PrimeQ[i+8]], i=i+10]; {i,i+2,i+6,i+8}]] мы в течение секунд увидим что-нибудь в духе 1000000000000000081721 1000000000000000081723 1000000000000000081727 1000000000000000081729 322 Для чисел небольшого порядка обычно это требует не больше миллиона итераций. Это значит, что четверок очень много. 1.12. Найдите первые 100 простых вида n 2 + 1. 1.13. Найдите первые 100 простых вида n 2 + n + 1. 2. Теорема Эвклида. 113 В десятой книге “Элементов” Эвклида содержится следующее утвержде- ние, известное как теорема Эвклида: множеcтво рациональных проcтых чиcел беcконечно. Основная идея доказательства теоремы Эвклида состоит в том, чтобы построить бесконечную последовательность попарно взаимно простых чисел 6= 1. Особенно выпукло использованный для этого прием можно выразить следующим образом. Пусть n 1 , . . . , n s — любые натуральные числа. Тогда число n 1 . . . n s + 1 взаимно просто с каждым из n 1 , . . . , n s Определим теперь рекуррентно последовательность чисел E i , i ∈ N, полагая E 1 = 2 и E i = E 1 . . . E i −1 + 1 для всех i ≥ 2. В силу только что сказанного все E i представляют собой попарно взаимно простые числа > 1. Пусть теперь q i — наименьший простой делитель числа E i . Тогда все q i , i ∈ N, попарно различные простые числа. Кнут предложил называть E i числами Эвклида. Таким образом, они имеют бесконечно много различных простых делителей. С другой стороны, Одони 114 доказал, что имеется бесконечно много простых чисел, которые не делят ни одно из чисел Эвклида. Ясно, что E 2 = 2 + 1 = 3, E 3 = 2 · 3 + 1 = 7, E 4 = 2 · 3 · 7 + 1 = 43. Обратите внимание, что все это простые числа! 2.1. Напишите рекуррентную программу для вычисления чисел Эвклида. Верно ли что все они простые? Ответ. Нет, уже следующее число Эвклида E 5 = 2 · 3 · 7 · 43 + 1 = 1807 не простое: 1807 = 13 · 139. Число E 6 = 3263443 снова простое, но, насколько нам известно, среди E n , n ≥ 7, не удалось найти ни одного простого числа. Большинство специалистов верят, что все они составные. 2.2. Найдите разложения нескольких следующих чисел Эвклида E n на простые. В тех случаях, когда это невозможно, найдите какие-то их про- стые делители. Указание. Попробуйте использовать функцию FactorInteger. Ответ. Так как при переходе от числа Эвклида E n к числу Эвклида E n+1 количество цифр почти удваивается, то в E 30 уже больше 109 миллионов 113 I was interviewed in the Israeli Radio for five minutes and I said that more than 2000 years ago, Euclid proved that there are infinitely many primes. Immediately the host interuppted me and asked: “Are there still infinitely many primes?” c Noga Alon 114 R.W.K.Odoni, On the prime divisors of the sequence w n+1 = 1 + w 1 w 2 . . . w n . — J. London Math. Soc. 1985, vol.32, p.1–11. 323 цифр. Поскольку числа Эвклида — и их наименьшие простые делители! — настолько быстро растут, уже при n ≥ 11 поиск их явных разложений на простые множители на бытовом компьютере при помощи элементарных ме- тодов чрезвычайно затруднителен или прямо невозможен. Вот разложения нескольких первых из них: E 7 = 10650056950807 = 547 · 607 · 1033 · 31051, E 8 = 113423713055421844361000443 = 29881 · 67003 · 9119521 · 6212157481, E 9 = 12864938683278671740537145998360961546653259485195807 = 5295435634831 · 31401519357481261 · 77366930214021991992277, Уже число E 10 содержит 105 знаков, поэтому ограничимся указанием тех простых делителей нескольких следующих чисел, которые ищутся относи- тельно быстро: E 10 181 1987 112374829138729 E 11 2287 E 12 73 E 13 2589377038614498251653 E 14 52387 5020387 5783021473 E 15 13999 74203 9638659 Обратите внимание, что двадцатидвухразрядное число, указанное в каче- стве простого множителя числа Эвклида E 13 действительно является про- стым! Однако сам Эвклид использовал для доказательства бесконечности мно- жества простых не числа Эвклида, а примориалы. Пусть q простое число. Произведение q# = Q p всех простых p ≤ q не превосходящих q называет- ся примориалом числа q. Обозначение q# было предложено в 1987 году Дабнером 115 и в настоящее время стало общепринятым. Так как q# делит- ся на все простые ≤ q, то ни q# + 1 ни q# − 1 не делятся ни на одно из них и, значит, содержат новые простые делители. Довольно часто эти числа содержат очень большие простые множители, а в некоторых случаях сами являются большими простыми (primorial primes). В следующих задачах простой множитель q числа n называется большим, если q > n/q, и, кроме того, в случае, когда n/q = p само является простым, q > p 2 2.3. Сколько среди чисел вида n# + 1, 1 ≤ n ≤ 50, простых? Ответ. Никаких других простых, кроме очевидных 2# + 1 = 3, 3# + 1 = 7, 5# + 1 = 31, 7# + 1 = 211 и 11# + 1 = 2311 не просматривается. 2.4. Вычислите разложение на множители чисел вида n# + 1, n ≤ 50. Какое наибольшее количество различных простых множителей при этом встречается? В каких случаях встречаются большие простые множители? 2.5. Сколько среди чисел вида n# − 1, 1 ≤ n ≤ 50, простых? 115 H.Dubner, Factorial and primorial primes. — J. Recr. Math., 1987, vol.19, p.197–203. 324 Ответ. А вот здесь, кроме очевидных простых 3# − 1 = 5, 5# − 1 = 29, 11# − 1 = 2309 и 13# − 1 = 30029 есть еще одно, уже совсем не очевидное: 89# − 1 = 23768741896345550770650537601358309. 2.6. Вычислите разложение на множители чисел вида n# − 1, 1 ≤ n ≤ 50. Какое наибольшее количество различных простых множителей при этом встречается? В каких случаях встречаются большие простые множители? Вместо примориалов для доказательства теоремы Эвклида можно было бы использовать и факториалы. Снова n! делится на все простые ≤ n и, значит, n! + 1 и n! − 1 содержат новые простые делители. Опять же, очень часто эти числа содержат громадные простые множители, а в некоторых случаях и сами являются простыми (factorial primes). 2.7. Сколько среди чисел вида n! + 1, 2 ≤ n ≤ 50 простых? Квадратов простых? Ответ. Кроме очевидных случаев 1! + 1 = 2, 2! + 1 = 3, 3! + 1 = 7 простыми оказываются только 11! + 1 = 39916801, 27! + 1 = 10888869450418352160768000001, 37! + 1 = 13763753091226345046315979581580902400000001, 41! + 1 = 33452526613163807108170062053440751665152000000001. Единственные квадраты простых встречаются в самом начаале: 4! + 1 = 25 = 5 2 , 5! + 1 = 121 = 11 2 и 7! + 1 = 5041 = 71 2 2.8. Вычислите разложение на множители чисел вида n! + 1, e ≤ n ≤ 50. Какое наибольшее количество различных простых множителей при этом встречается? В каких случаях встречаются большие простые множители? 2.9. Сколько среди чисел вида n! − 1, 2 ≤ n ≤ 50, простых? Ответ. Кроме очевидных случаев 3! − 1 = 5, 4! − 1 = 23, 6! − 1 = 719 и 7! − 1 = 5039 простыми оказываются только 12! − 1 = 479001599, 30! − 1 = 265252859812191058636308479999999, 32! − 1 = 263130836933693530167218012159999999, 33! − 1 = 8683317618811886495518194401279999999, 38! − 1 = 523022617466601111760007224100074291199999999. 2.10. Вычислите разложение на множители чисел вида n! + 1, 2 ≤ n ≤ 50. Какое наибольшее количество различных простых множителей при этом встречается? В каких случаях встречаются большие простые множители? 3. Теорема Банга-Жигмонди. 116 116 I can do without essentials but I must have my luxuries. c Oscar Wilde 325 В действительности, чтобы найти бесконечное количество простых чи- сел, не обязательно даже, чтобы члены последовательности были попарно взаимно просты, достаточно, чтобы (начиная с некоторого места) каждый следующий член имел примитивный простой делитель, не являющийся делителем ни одного из предыдущих членов этой последовательности. Оказывается, каждая пара взаимно простых натуральных чисел x > y порождает такую последовательность, n-м членом которой является x n − y n . Банг (1886 год, в частном случае y = 1) и Жигмонди 117 (1892 год, в общем случае) обнаружили следующий исключительно важный факт, очень часто используемый в теории чисел, комбинаторике и теории групп: x n − y n почти всегда имеет примитивный простой делитель, который не делит никакую из разностей x m − y m при m < n. В дальнейшем теорема Банга—Жигмонди многократно переоткрывалась и известна под разными названиями. В старых учебниках теории чисел она чаще всего называется теоремой Биркгофа—Вандивера 118 Одним из забавных следствий этой теоремы является утверждение, что для любого s существует простое число p такое, что десятичное разложение 1/p имеет период s. Очевидные исключения получаются здесь при n = 1 и x = y + 1 и при n = 2, x + y = 2 k для некоторого k. Кроме того, имеется еще одно не совсем очевидное исключение. 3.1. Имеется еще ровно одна тройка (x, y, n), для которой x n − y n не имеет примитивных простых делителей. Найдите ее. Ответ. Организовав полный перебор легко обнаружить, что при x = 2, y = 1, и n = 6 число 2 6 − 1 = 63 = 3 2 · 7 не имеет примитивных простых делителей: 2 2 − 1 = 3 и 2 3 − 1 = 7. 3.2. Укажите для каждого n ≤ 150 наименьший примитивный простой делитель 2 n − 1. Что можно сказать об их величине? Решение. Обозначим наименьший простой делитель 2 n −1 через q n . Мно- жество всех новых простых делителей 2 n − 1 можно найти, например, так: new[n ]:=Complement[First[Transpose[FactorInteger[2^n-1]]], Apply[Union,Table[ First[Transpose[FactorInteger[2^i-1]]], {i,2,n-1}]]] Теперь q n это просто первый элемент new[n]. Начало ответа легко посчи- тать в уме: q 2 = 3, q 3 = 7, q 4 = 5, q 5 = 31, q 7 = 127, q 8 = 17, q 9 = 73, 117 K.Zsigmondy, Zur Theorie der Potenzreste. — Monatshefte Math. Phys., 1892, Bd.3, S.265–284. 118 G.D.Birkhoff, H.S.Vandiver, On the integral divisors of a n − b n . — Ann. Math., 1904, vol.5, p.173–180. 326 q 10 = 11. Вот еще несколько значений: q 11 = 23 q 12 = 13 q 13 = 8191 q 14 = 43 q 15 = 151 q 16 = 257 q 17 = 131071 q 18 = 19 q 19 = 524287 q 20 = 41 q 21 = 337 q 22 = 683 q 23 = 47 q 24 = 241 q 25 = 601 q 26 = 2731 q 27 = 262657 q 28 = 29 q 29 = 233 q 30 = 331 q 31 = 2147483647 q 32 = 65537 q 33 = 599479 q 34 = 43691 q 35 = 71 q 36 = 37 q 37 = 223 q 38 = 174763 q 39 = 79 q 40 = 61681 q 41 = 13367 q 42 = 5419 q 43 = 431 q 44 = 397 q 45 = 631 q 46 = 2796203 q 47 = 2351 q 48 = 97 q 49 = 4432676798593 q 50 = 251 3.3. Укажите для каждого n ≤ 120 наименьший примитивный простой делитель 3 n − 1. А теперь выберете те n, для которых (3 n − 1)/2 простое. 3.4. Укажите для каждого n ≤ 110 наименьший примитивный простой делитель 3 n − 2 n . А теперь попробуйте найти его еще для 10 значений n. Как Вы думаете, с чем связан столь резкий рост времени, необходимого для факторизации? Ответ. Около 5/6 этого времени идет на факторизацию одного числа, а именно, 3 118 − 2 118 = 5 · 19471 · 145142890373531870546641· 14130386091162273752461387579 Множители с 24 и 29 цифрами достаточно близки для того, чтобы система могла их найти с помощью квадратичного решета, но недостаточно близки для того, чтобы она могла это сделать за секунду. 3.5. Убедитесь, что если x и y взаимно просты, то каждый примитивный простой делитель p числа x n − y n удовлетворяет сравнению p ≡ 1 (mod n). 3.6. Что будет, если заменить последовательность x n − y n на последова- тельность x n +y n ? Всегда ли верно, что x n +y n имеет примитивный простой делитель, не делящий никакую из сумм x m + y m при m ≤ n, или тут тоже есть исключения? Вот еще одна забавная иллюстрация теоремы Банга—Жигмонди. 3.7. Исследуйте факторизацию чисел (p 1 . . . p n + 1) 2 m − 1, где p 1 , . . . , p n суть первые n нечетных простых и убедитесь, что это произ- ведение имеет не менее n + m различных простых делителей. 327 4. Простые Мерсенна. 119 В этом и следующем пунктах мы обсудим два важнейших классических класса простых, возникающие во многих вопросах теории чисел, алгебры и комбинаторики. Если m — собственный делитель n, то x n −1 делится на x m −1. Поэтому если M n = 2 n −1 простое, то n простое. Большинство ранних авторов были уверены, что верно и обратное, т.е. если p простое, то M p тоже простое. Это заблуждение было развеяно в 1536 году Худальрикусом Региусом, который заметил, что M 11 − 1 = 23 · 89. В 1588 году Пьетро Катальди проверил, что M 17 и M 19 простые, при этом он заявил, что M 23 , M 29 , M 31 и M 37 тоже простые. В 1640 году Пьер Ферма проверил, что в действительности M 23 и M 37 составные. Позже Эйлер заметил, что M 29 составное, а в 1772 году он показал, что M 31 простое. В связи с проблемой четных совершенных чисел Марин Мерсенн в 1644 году утверждал, что числа M p , p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257 просты, а все остальные числа M p для p ≤ 257 составные. Как позже выяснилось, этот список содержал ошибки. Числа вида M p = 2 p − 1, где p простое, называются числами Мерсенна. Почти все самые большие известные простые числа являются числами Мерсенна. 4.1. Найдите первые 15 простых чисел Мерсенна и исправьте все ошибки в его списке. Ответ. Можно, например, так: Select[Table[2^Prime[n]-1, {n,1,300}],PrimeQ] Топорно, но для таких маленьких чисел это не имеет никакого значения. Напомним, что функция Select[list,crit] осуществляет выбор элемен- тов из списка list, в данном случае из списка первых 300 чисел вида 2 p −1, где p простое, удовлетворяющих критерию crit, в данном случае крите- рию PrimeQ, осуществляющему проверку 2 p − 1 на простоту. При этом получится ровно 15 простых, а именно, 119 The trouble with integers is that we have examined only the very small ones. Maybe all the exciting stuff happens at really big numbers, ones we can't even begin to think about in any very definite way. Our brains have evolved to get us out of the rain, find where the berries are, and keep us from getting killed. Our brains did not evolve to help us grasp really large numbers or to look at things in a hundred thousand dimensions. c Ronald L. Graham 328 M 2 = 3 M 3 = 7 M 5 = 31 M 7 = 127 M 13 = 8191 M 17 = 131071 M 19 = 524287 M 31 = 2147483647 M 61 = 2305843009213693951 M 89 = 618970019642690137449562111 M 107 = 162259276829213363391578010288127 M 127 = 170141183460469231731687303715884105727 и M 521 , M 607 , M 1279 , которые слищком велики, чтобы воспроизводить их здесь. Заметим, что на протяжении 75 лет M 127 оставалось самым большим из- вестным простым числом. А именно, используя сформулированный чуть ниже критерий Люка—Лемера в 1876 году Люка доказал, что M 127 простое. Только в 1951 году удалось найти большие простые числа. Некоторые счи- тают, впрочем, что первое безукоризненное доказательство простоты M 127 было дано только в 1894 году Фокембергом, но даже и в этом случае ре- корд простоял 57 лет! Еще дольше, 84 года, продержался рекорд простого числа, не являющегося числом Мерсенна, установленный Ландри в 1867 году, а именно, M 59 /179951. Вот все остальные индексы p, для которых сегодня (весна 2006 года) известно, что число Мерсенна M p является простым: 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 20996011, 24036583, 25964951, 30402457 Последние из этих чисел M p настолько велики, что для десятичной записи каждого из них нужно несколько книг объемом 1000 страниц. Например, число M 30402257 содержит 9152052 десятичные цифры. 4.2. Породите первые 15 пар вида (p, M p ), где M p простое Мерсенна. Ответ. Можно, например, так Select[Table[ {Prime[n],2^Prime[n]-1},{n,1,300}], PrimeQ[#[[2]]]&] Обратите внимание на использование критерия в формате анонимной функции! Дело в том, что в данном случае производится не проверка про- стоты элемента списка, а проверка простоты второй части этого элемента. 329 Не забывайте, что вызов анонимной функции должен заканчиваться ам- персандом. Проверять простоту числа M p значительно проще, чем простоту дру- гих чисел того же порядка. Это связано с тем, что для них имеется сле- дующий критерий простоты, открытый в 1876 году Люком (alias Лукас, Lucas) и упрощенный в 1930 году Лемером. Чтобы сформулировать этот критерий, определим прежде всего числа Люка L n . Положим L 1 = 4 и зададим следующие числа рекуррентно посредством L n+1 = L 2 n − 2. 4.3. Напишите программу для вычисления чисел Люка. Ответ. Поскольку рекуррентная программа очевидна, ограничимся пере- числением нескольких первых L n : L 2 = 14, L 3 = 194, L 4 = 37634, L 5 = 1416317954, L 6 = 2005956546822746114, L 7 = 4023861667741036022825635656102100994. Числа Люка растут довольно быстро растут, уже у L 100 больше, чем 10 27 цифр. Так вот, критерий Люка—Лемера утверждает, что для того, чтобы выяснить, является ли число Мерсенна M p простым, необходимо выпол- нить всего одно деление, а именно, M p в том и только том случае простое, когда оно делит L p −1 4.4. Напишите тест простоты чисео Мерсенна, основанный на критерии Люка—Лемера и сравните скорость его работы с PrimeQ. Обратимся теперь к разложению на простые множители тех чисел Мер- сенна, которые не являются простыми. Заметим, что поиск простых дели- телей резко упрощается следующим критерием Ферма—Эйлера. Пусть p и q — нечетные простые. Тогда если p |M q , то p ≡ 1 (mod q), p ≡ ±1 (mod 8). 4.5. Разложите на множители все остальные числа Мерсенна до M 127 Ответ. Поскольку все эти числа имеют небольшие делители, можно обой- тись функцией FactorInteger. 330 M 11 = 2047 = 23 · 89, M 23 = 8388607 = 47 · 178481, M 29 = 536870911 = 233 · 1103 · 2089, M 37 = 137438953471 = 223 · 616318177, M 41 = 2199023255551 = 13367 · 164511353, M 43 = 8796093022207 = 431 · 9719 · 2099863, M 47 = 140737488355327 = 2351 · 4513 · 13264529, M 53 = 9007199254740991 = 6361 · 69431 · 20394401, M 59 = 576460752303423487 = 179951 · 3203431780337, M 67 = 147573952589676412927 = 193707721 · 761838257287, M 71 = 228479 · 48544121 · 212885833, M 73 = 439 · 2298041 · 9361973132609, M 79 = 2687 · 202029703 · 1113491139767, M 83 = 167 · 57912614113275649087721, M 97 = 11447 · 13842607235828485645766393, M 101 = 7432339208719 · 341117531003194129, M 103 = 2550183799 · 3976656429941438590393, M 109 = 745988807 · 870035986098720987332873, M 113 = 3391 · 23279 · 65993 · 1868569 · 1066818132868207, M 131 = 263 · 10350794431055162386718619237468234569, M 137 = 32032215596496435569 · 5439042183600204290159, M 139 = 5625767248687 · 123876132205208335762278423601, M 149 = 86656268566282183151 · 8235109336690846723986161, M 151 = 18121 · 55871 · 165799 · 2332951 · 7289088383388253664437433, M 157 = 852133201 · 60726444167 · 1654058017289 · 2134387368610417, M 163 = 150287 · 704161 · 110211473 · 27669118297 · 36230454570129675721, M 167 = 2349023 · 79638304766856507377778616296087448490695649, M 173 = 730753 · 1505447 · 70084436712553223 · 155285743288572277679887, 4.6. А теперь напишите программу поиска делителей M p , использующую критерий Ферма—Эйлера, которая работает быстрее, чем FactorInteger. Бросается в глаза наличие у некоторых M p совсем маленьких простых делителей, скажем 23 |M 11 , 47 |M 23 и 167 |M 83 . Оказывается, это не случай- ность. А именно, критерий Эйлера—Лагранжа утверждает, что если p ≡ 3 (mod 4), то q = 2p + 1 в том и только том случае является простым, когда q |M p 4.7. Найдите все p < 1000 такие, что q = 2p + 1 делит M p 331 5. Простые Ферма. 120 Начнем со следующего незамысловатого наблюдения 5.1. Проверьте (или докажите!), что если 2 m + 1, где m ∈ N, простое, то m = 2 n , n ∈ N 0 Число вида F n = 2 2 n + 1, где n ∈ N 0 , называется числом Ферма. Числа Ферма возникают в самых различных вопросах теории чисел, комбинатори- ки, алгебры и геометрии. Интересно заметить, что сам Ферма достаточно определенно утверждал, что все числа Ферма F n простые, но смог прове- рить лишь, что F 0 = 3, F 1 = 5, F 2 = 17, F 3 = 257, F 4 = 65537 просты. 5.2. Подтвердите или опровергните утверждение Ферма. Ответ. Приведенные выше пять чисел являются единственными извест- ными сегодня простыми числами Ферма! В 1732 году Эйлер нашел разло- жение на множители следующего числа Ферма F 5 = 4294967297 = 641 · 6700417 = (2 7 5 + 1)(2 7 52347 + 1). Число F 6 тоже легко раскладывается на множители: F 6 = 18446744073709551617 = 274177 · 67280421310721 = (2 8 1071 + 1)(2 8 262814145745 + 1). В это большинстве классических книг по теории чисел утверждается, что это разложение было найдено в 1880 году Ландри и Ле Лассером. Одна- ко в 1964 году К.Бирманн обнаружил, что что Томас Клаузен привел эту факторизацию в письме к Гауссу, датированном 1 января 1855 года, и что он знал, что оба множителя простые! А вот разложить на множители число F 7 в докомпьютерную эпоху не было никакой возможности. В действительности, следующее разложение было найдено лишь в 1970 году 121 : F 7 = 59649589127497217 · 5704689200685129054721 = (2 9 116503103764643 + 1)(2 9 11141971095088142685 + 1). Число F 8 , было факторизовано лишь в 1980 году 122 : F 8 = 1238926361552897 · 93461639715357977769163558199606896584051237541638188580280321 = (2 11 604944512477 + 1) (2 11 45635566267264637582599393652151804972681268330878021767715 + 1) 120 Мы всегда готовы говорить правду. Но как мы ее узнаем? c Леонид Шебаршин, Заметки бывшего начальника разведки 121 M.A.Morrison, J.Brillhart, The factorisation of F 7 . — Bull. Amer. Math. Soc., 1971, vol.77, p.264. 122 R.P.Brent, J.M.Pollard, The factorisation of the eighth Fermat number. — Math. Comput., 1981, vol.36, p.627–630. 332 Приятно, что сегодня это разложение за секунды ищется на бытовом ком- пьютере при помощи функции FactorInteger. Что касается F 9 , то в 1903 году Вестерн обнаружил, что оно делится на 2 16 37 + 1 = 2424833. Несмотря на это полная факторизация F 9 на множите- ли была получена лишь в 1990 году 123 При этом оказалось, что два других делителя числа F 9 содержат 46 и 96 цифр, соответственно. Единственными другими числами Ферма, которые сегодня полностью разложены на простые множители, являются F 10 и F 11 , смотри 124 . Для всех остальных чисел Ферма известны лишь какие-то простые делители, но не полная факторизация. Вот начало факторизации F 10 : F 10 = (2 12 11131 + 1)(2 14 395937 + 1) . . . два пропущенных делителя содержат 40 и 252 цифр, соответственно. Вот начало факторизации F 11 : F 11 = (2 13 39 + 1)(2 13 119 + 1)(2 14 10253207784531279 + 1) (2 13 434673084282938711 + 1) . . . и еще один делитель, содержащий 564 цифр. Вычислительная сложность этой задачи растет невероятно быстро с ро- стом n. Числа Ферма F 12 , F 13 , F 14 и F 15 имеют 1234, 2467, 4933, 9865 разря- дов, соответственно. Даже установление простоты чисел такого порядка на бытовых компьютерах может оказаться проблематичным, а искать разло- жение таких чисел на множители сегодня мы просто не умеем. Вот начало факторизации F 12 : F 12 = (2 14 7 + 1)(2 16 397 + 1)(2 16 973 + 1)(2 14 11613415 + 1) (2 14 76668221077 + 1) . . . Вот начало факторизации F 13 : F 13 = (2 16 41365885 + 1)(2 17 20323554055421 + 1)(2 19 6872386635861 + 1) (2 19 609485665932753836099 + 1) . . . . Однако, оказывается, что узнать, является ли число Ферма F n простым, совсем просто. Например, сегодня мы не знаем никаких простых делителей чисел Ферма F 14 F 20 , F 22 , F 24 и многих других. В то же время известно, что эти числа не являются простыми. Это устанавливается при помощи следующего легко проверяемого теста, известного как критерий Пепина. 123 A.K.Lenstra, H.W.Lenstra, M.S.Manasse, J.M.Pollard, The factorisation of the ninth Fermat number. — Math. Comput., 1993, vol.61, p.319–149. 124 R.P.Brent, Factorisation of the tenth Fermat number. — Math. Comput., 1999, vol.68, p.429–451. 333 Для того, чтобы число Ферма F n , n > 1, было простым, необходимо и достаточно, чтобы 3 (F n −1)/2 ≡ −1 (mod F n ). 5.3. Проверьте, что числа F n , n = 10, . . . , 15, не являются простыми. Указание. Непосредственно возвести 3 в степень такого порядка нет шан- сов, поэтому используйте функцию PowerMod. Посмотрите, какой остаток она возвращает и аккуратно сформулируйте условие! Обратимся теперь к задаче поиска простых делителей чисел Ферма. Не следует думать, что Эйлер настолько любил считать, чтобы делить вруч- ную 10-значное число на все простые подряд, пока случайно не наткнулся на делитель 641. В действительности, ему пришлось для этого выполнить всего одно или два деления, а, скорее всего, ни одного. Реконструируем рассуждения Эйлера, чтобы читатель мог на этом игру- шечном примере представить, при помощи каких примерно соображений ищутся простые делители у чисел, содержащих многие сотни или тысячи десятичных знаков, если известна их структура. Дело в том, что для того, чтобы разложить число Ферма F n на множители, достаточно прове- рять не все простые p ≤ √ F n , а лишь простые вида p = 2 n+1 m + 1, где m ∈ N. Это вытекает из следующего легко проверяемого соображения, из- вестного как сравнение Эйлера: любой делитель числа F n , n ≥ 3, имеет вид 2 n+2 m + 1, для некоторого m ∈ N. В силу сравнения Эйлера делителями F 5 могут быть только простые числа вида p = 128m + 1. Первые два таких числа, это p = 257 и p = 641, которые получаются при m = 2 и m = 5, соответственно. Однако очевидно, что 641 = 2 4 +5 4 делит a = 2 32 +2 28 5 4 . С другой стороны, применяя форму- лу для разности квадратов, мы видим, что 641 = 2 7 5 + 1 делит b = 2 28 5 4 −1. Таким образом, 641 делит и разность этих чисел F 5 = a −b. Для того, чтобы проверить, будет ли 6700417 простым, достаточно, в худшем случае, про- извести еще не более 4 делений, а именно, проверить, что оно не делится на простые числа вида p = 128m + 1, 5 ≤ m ≤ 20, каковых, очевидно (см. таблицу простых) ровно 4, а именно, 641, 769, 1153, 1409. Однако, зная Эйлера, можно предположить, что он, скорее всего, и здесь обошелся вооб- ще без явных вычислений. Экстраполируя этот пример, мы понимаем, что сказано в эпиграфе к этому параграфу: один изобретательный математик может с успехом заменить сотни вычислителей. 5.4. А теперь напишите программу, раскладывающую числа F 6 , F 7 и F 8 на множители быстрее, чем это делает внутренняя команда FactorInteger. Приведем список известных небольших простых делителей нескольких следующих чисел Ферма: 334 F 15 2 21 579 + 1, 2 17 17753925353 + 1, 2 17 1287603889690528658928101555 + 1 F 16 2 19 1575 + 1, 2 20 180227048850079840107 + 1 F 17 2 19 59251857 + 1 F 18 2 20 13 + 1 F 19 2 21 33629 + 1, 2 21 308385 + 1 F 21 2 23 534689 + 1 F 23 2 25 5 + 1 F 25 2 29 48413, 29 + 1, 2 27 1522849979 + 1, 2 27 16168301139 + 1 F 26 2 29 143165 + 1 F 27 2 30 141015 + 1, 2 29 430816215 + 1 F 28 2 36 25709319373 + 1 F 29 2 31 1120049 + 1 F 30 2 32 149041 + 1, 2 33 127589 + 1 Заметим, что числа Ферма дают еще один подход к доказательству тео- ремы Эвклида бесконечности числа простых. В самом деле, из следующей задачи (взятой непосредственно из переписки Гольдбаха и Эйлера 125 ) вы- текает, что числа Ферма попарно взаимно просты. 5.5. Проверьте (или докажите!), что F 0 F 1 F 2 . . . F n = F n+1 − 2. Таким образом, если F m делит F n , при некотором n > m, то F m делит 2, что невозможно. Рассматриваются различные вариации на тему чисел Ферма. Вот три наиболее известные из них. • Числа вида b 2 n +1 называется обобщенными числами Ферма 126,127 , обычные числа Ферма получаются здесь при b = 2. • Число C n = n · 2 n + 1 называется числом Каллена. • Число W n = n · 2 n − 1 называется числом Вудалла. 125 Доказательство, основанное на той же идее, но содержащее несколько чрезвычайно удачных ухудшений, воспроизводится в книге “Задачи и теоремы из анализа”, поэтому некоторые авторы ошибочно приписывают его Пойа и Сеге. 126 H.Dubner, W.Keller, Factors of generalized Fermat numbers. — Math. Comput., 1995, vol.64, p.397–405. 127 A.Bj¨ orn, H.Riesel, Factors of generalized Fermat numbers. — Math. Comput., 1998, vol.67, p.441–446. 335 5.6. Вычислите первые 140 чисел Каллена C n = n · 2 n + 1 и убедитесь, что все они, кроме C 1 = 3 составные. Достаточно ли этого, чтобы сформули- ровать гипотезу, что все числа C n , n > 1, составные? Ответ. Нет, число C 141 простое 128 . Кроме того, известны следующие про- стые Каллена 129,130 : C 4713 , C 5795 , C 6611 , C 18496 , C 32292 , C 32469 , C 59656 , C 90825 , C 262419 , C 361275 , C 481899 . В отличие от простых Каллена, среди простых Вудалла с небольшими индексами достаточно много простых. 5.7. Найдите первые 15 чисел Вудалла W n = n · 2 n − 1. Ответ. Вот они: W 2 = 7, W 3 = 23, W 6 = 383, W 30 = 32212254719, W 75 = 2833419889721787128217599, W 81 = 195845982777569926302400511, W 115 = 4776913109852041418248056622882488319, W 123 = 1307960347852357218937346147315859062783, и, кроме того, W 249 , W 362 , W 384 , W 462 , W 512 , W 751 , W 822 . Следующие про- стые Вудалла непомерно велики: W 5312 , W 7755 , W 9531 , W 12379 , W 15822 , W 18885 , W 22971 , W 23005 , W 98726 , W 143018 , W 151023 , W 667071 . 6. Распределение простых. 131 Обозначим через π(n) количество натуральных простых не превосходя- щих n ∈ N. Ясно, что если n = p ∈ P простое, то π(p) = π(p − 1) + 1. Напомним, что в соответствии с общим приницпом образования имен на языке Mathematica функция π называется PrimePi. 6.1. Составьте таблицу значений функций π(n) и n/π(n) для n = 10 m , 1 ≤ m ≤ 14, и сравните вычисленные значения с ln(n). 128 R.M.Robinson, A report on primes of the form k · 2 n + 1 and on factors of Fermat numbers. — Proc. Amer. Math. Soc., 1958, vol.9, p.673–681. 129 W.Keller, Factors of Fermat numbers and large primes of the form k · 2 n + 1. — Math. Comput., 1983, vol.41, p.661–673. 130 W.Keller, New Cullen primes. — Math. Comput., 1995, vol.64, p.1733–1741. 131 Nature is a good approximation of Mathematics c Zvi Artstein 336 Ответ. Вот как выглядят эти значения: n π(n) n/π(n) ln(n) 10 4 2.5 2.30259 100 25 4. 4.60517 1000 168 5.95238 6.90776 10000 1229 8.1367 9.21034 1 00000 9592 10.4254 11.5129 10 00000 78498 12.7392 13.8155 100 00000 6 64579 15.0471 16.1181 1000 00000 57 61455 17.3567 18.4207 10000 00000 508 47534 19.6666 20.7233 1 00000 00000 4550 52511 21.9755 23.0259 10 00000 00000 41180 54813 24.2833 25.3284 100 00000 00000 3 76079 12018 26.5901 27.6310 1000 00000 00000 34 60655 36839 28.8963 29.9336 10000 00000 00000 320 49417 50802 31.2018 32.2362 Эта таблица показывает, что маленьких простых чисел довольно много: скажем, среди первых 10000 чисел 1229 простых — больше, чем 12%. В действительности, среди первого миллиарда натуральных чисел все еще больше 5% простых!!! Глядя — в пятнадцатилетнем возрасте! — на такую, или чуть более ко- роткую, таблицу, Гаусс заметил, что, при переходе от каждой степени 10 к следующей, отношение n/π(n) увеличивается примерно на ln(10) ∼ = 2.30259. Это натолкнуло его на замечательное предположение, что при n стремя- щемся к ∞ функция n 7→ π(n) растет примерно как n 7→ n/ ln(n). Утвер- ждение об асимптотической эквивалентности π(n) и n/ ln(n) называется асимптотическим законом распределения простых чисел или, иногда, просто теоремой о простых числах. Первое выдающееся продвижение в направлении доказательства асимп- тотического закона получил в 1849 году П.Л.Чебышев. Однако, полностью асимпотический закон распределения простых был доказан лишь в 1896 году независимо Адамаром и де ла Валле-Пуссеном с использованием тео- рии функций комплексной переменной. Запомнить дату 1896 чрезвычайно легко, поскольку Адамар прожил 98 лет, а де ла Валле-Пуссен — 96. Ри- бенбойм выражает уверенность, что это произошло именно как следствие того, что они доказали столь замечательную теорему. Элементарное до- казательство асимптотического закона нашли Сельберг 132 и Эрдеш в 1949 году. При изучении подгрупп в симметрической группе Жозеф Бертран ис- пользовал следующее утверждение, известное как постулат Бертрана: при n > 7 между n/2 и n − 2 всегда содержится хотя бы одно простое 132 A.Selberg, An elementary proof of the prime number theorem. — Ann. Math., 1951, vol.85, p.203–362. 337 число. Сам Бертран проверил это утверждение для всех n < 1500000, но его доказательством в общем случае он не владел. Первое доказательство постулата Бертрана придумал в 1852 году П. Л. Чебышев. 6.2. Проверьте постулат Бертрана для всех n ≤ 2000000. Шинцель предложил следующее усиление постулата Бертрана, извест- ное как гипотеза Шинцеля: для каждого n ≥ 117 между n и n + √ n найдется хотя бы одно простое число. 6.3. Проверьте гипотезу Шинцеля для всех 117 ≤ n ≤ 100000. Как Вы думаете, с чем связано ограничение n ≥ 117? Верно ли, что для любых x, y ≥ 2 выполняется неравенство π(x + y) ≤ π(x) + π(y)? 6.4. Проверьте выполнение этого неравенства для всех x, y ≤ 1000. 7. Теорема Дирихле. 133 В простейшем варианте знаменитая теорема Дирихле о простых в арифметических прогрессиях, с которой собственно и начинается совре- менная аналитическая теория чисел, утверждает, что для любых взаимно простых a и d в арифметической прогрессии a + nd, n ∈ N, бесконечно мно- го простых. В частности, существует бесконечно много простых с любыми наперед заданными m последними цифрами, если только последняя цифра не равна 0, 2, 4, 5, 6, 8. Однако, как мы сейчас увидим, в действительности теорема Дирихле утверждает гораздо больше, чем просто бесконечность простых в арифме- тической прогрессии. 7.1. Найдите количество простых ≤ 10 6 , последняя цифра которых равна 1, 3, 7, 9. Решение. Вычисляя Map[Length[Select[Range[#,10^6,10],PrimeQ]]&, {1,3,7,9}] мы видим, что количество простых с последней цифрой 1, 3, 7, 9 практи- чески не зависит от этой цифры: Вот как распределяются по последней цифре 78498 простых чисел меньших одного миллиона: 19617, 19665, 19621, 19593. Эта закономерность становится еще очевиднее, если продолжить вычисле- ния. Вот как распределяются по последней цифре 664579 простых чисел меньших десяти миллионов: 166104, 166230, 166211, 166032, 133 Какое чудо, если есть Тот, кто затеплил в нашу честь Ночное множество созвездий ! А если всё само собой Устроилось, тогда, друг мой, Еще чудесней! c Александр Кушнер 338 и вот, наконец, 5761455 простых чисел меньших ста миллионов: 1440299, 1440474, 1440495, 1440186 Мы видим, что каждый раз количество простых с данной последней циф- рой почти в точности равно четверти общего количества простых. Не бой- тесь повторить последнее вычисление - на персональном компьютере класса Intel Core 7 с оперативной памятью 8ГБ процесс займет около минуты. Взглянем теперь на последние две цифры. 7.2. Породите множество чисел, которые могут быть остатками простого числа по модулю 100. Решение. Как всегда, Mathematica дает почти бесконечное разнообразие способов решения этой задачи. Вот первые приходящие в голову: Map[FromDigits[#]&,Flatten[Outer[List,Range[0,9], {1,3,7,9}],1]] Select[Range[100],MemberQ[ {1,3,7,9},Last[IntegerDigits[#]]]&] Select[Range[100],MemberQ[ {1,3,7,9},Mod[#,10]]&] Select[Range[100],GCD[#,10]==1&] Apply[Union,Map[Range[#,100,10]&, {1,3,7,9}]] Конечно, при получении списка из 40 чисел вопрос выбора алгоритма явля- ется чисто схоластическим. Заметим, впрочем, что из приведенных выше определений последнее заведомо лучше предыдущих: оно лучше первого потому, что гораздо легче обобщается на любое количество цифр и лучше трех других потому, что не требует выбора по критерию из огромного спис- ка. Уже при порожении списка шестизначных чисел оно эффективнее раз в 50. 7.3. Найдите распределение простых ≤ 10 6 по последним двум цифрам. Ответ. Вот это распределение, где строки занумерованы цифрами 1, 3, 7, 9, а столбцы отвечают десяткам: 1964 1958 1937 1964 1955 1970 1960 1986 1942 1981 1969 1965 1976 1967 1959 1977 1962 1956 1969 1965 1932 1970 1976 1973 1956 1961 1943 1960 1984 1966 1957 1973 1926 1970 1960 1967 1955 1960 1958 1967 Снова в каждый класс попадает примерно одинаковое количество простых, а именно около 1/40 от общего количества. Теперь уже очевидно, что не только в каждой арифметической прогрес- сии содержится бесконечное количество простых, но и то, что простые рас- пределены равномерно между всеми прогрессиями основание которых вза- имно просто с фиксированной разностью d. Именно это, конечно, и утвер- ждает теорема Дирихле! 7.4. Проверьте утверждение теоремы Дирихле на других примерах. |