289-321, особенно с. 316] и усовершенствован Д. Г. Лемером [Annals of Math. 31 (1930), 419-448, особенно с. 443].

Этот способ проверки является частным случаем метода, применяемого в настоящее время для проверки принадлежности числа п к простым числам, когда известны множители числа п+1, и состоит в следующем.

Теорема L. Пусть q -нечетное простое число и последовательность (Ьп) задается правилом

Lo = 4, Ln+i = {Ll - 2) mod (2 - 1). (27)

Тогда число 2 - 1 будет простым тогда и только тогда, когда Lq-2 = 0.

Например, 2 - 1 - простое число, поскольку Li = (4 - 2) mod 7 = 0. Этот способ проверки особенно подходит для реализации на двоичных компьютерах из-за простоты вычислений по модулю (2 - 1) (см. раздел 4.3.2). В упр. 4.3.2-14 изложен способ, позволяющий сэкономить время выполнения операций в случае очень больших чисел q.

Доказательство. Докажем теорему L, используя лишь самые простые принципы теории чисел, путем исследования некоторых свойств рекуррентных последовательностей, представляющих и самостоятельный интерес. Рассмотрим последовательности {Un) и {Vn), определяемые правилами

f/o = 0, f/i = l, f/„+i =4f/„-f/„ i;

Vo = 2, Fi=4, y„+i =4У„-У„ 1.

По индукции легко доказать справедливость следующих соотношений:

VnUn+1-Un-i; (29)

f/„= ((2 + Уз)"-(2-Уз)")/\/12; (30)

У„ = (2 + Уз)" + (2-Уз)"; (31)

f/m+n = f/mf/n+l -f/m-lf/n. (32)

Докажем сейчас один вспомогательный результат, когда р - простое число и е > 1.

Если f/n = О (по модулю р), то f/„p н О (по модулю р+). (33)

Этот результат следует из более общих соображений, изложенных в упр. 3.2.2-11, но для соотношений (28) можно привести и непосредственное доказательство. Предположим, что Un = bp", Un+i = а. Согласно уравнению (32) и (28) имеем f/2n = bp{2a - АЬр") = 2aUn (по модулю р=+), а f/2n+i = f/+i -Ul = а. Аналогично f/зп = U2n+iUn - U2nUn-i = ZaUn и Uzn+i = U2n+iUn+i - U2nUn = a- В общем случае

Ukn = kaUn и Ukn+i = a (no модулю p=+).

Следовательно, взяв к = p, получим (33).

Из формул (30) и (31), раскрывая (2 ± \/3)" по биномиальной теореме, можно получить остальные выражения для [/„ и У„:

Un = j 2"-=-3 Vn = 2"-"+3. (34)

Положив теперь п = р, где р - нечетное простое число, и воспользовавшись тем фактом, что (1) кратно р, кроме случая, когда к = 0 или к = р, приходим к выводу, что

f/p = 3(P-i)/2 Vp = 4 (по модулю р). (35)

При р 7 3 по теореме Ферма имеем = 1; следовательно, {Zp~>/ - 1) х

(3{р-1)/2 + 1) = о и 3(Р-1)/2 = ±1. Если Up = -1, то Up+i = 4Up - Up-i = 4Up + Vp - Up+i = -f/p+i; отсюда f/p+i modp = 0. Если Up = +1, то Up-i = AUp - C/p+i = AUp - Vp - Up-i = ~Up-i; значит, Up-i modp = 0. Таким образом доказано, что для каждого простого р существует целое число с(р), такое, что

f7p+,f;,,modp = 0, £(р)<1. (36)

Далее, если N - произвол.,кое положительное целое число и если т = m{N) - такое наименьшее положительное целое число, что Um(n) mod iV = О, то

(7„modTV = 0 тогда и только тогда, когда п кратно m(TV). (37)

(Это число m{N) называется рангом появления в последовательности числа N.) Для доказательства (37) учтем, что последовательность Um, Um+i, Um+2, конгруэнтна (по модулю N) последовательности аЩ, aUi, af/2, • • •, где число а = Um+i xnod N взаимно просто с N, так как gcd(f7„, f/„+i) = 1.

После всех этих приготовлений докажем теорему L. В силу соотношения (27) по индукции имеем

Ln = Fan mod (2» - 1). (38)

Далее, из тождества 2Un+i = 4f/„ + У„ следует, что gcd(f/„,V„) < 2, поскольку всякий общий делитель чисел С/„ и У„ должен делить [/„ и 2f7„+i, в то время как и„ ± Un+i- Поэтому С/„ и У„ не имеют общих нечетных множителей, и, если Lq-2 = О, должно выполняться

с/г?-! = С/29-22,-2 О (по модулю 2» - 1), U21-2 О (по модулю 2 - 1).

Затем, если т = т(2 - 1) - ранг появления числа 2* - 1, то оно должно быть делителем Числа 2*~i, но не числа 2*"; таким образом, т = 2»~i. Докажем теперь, учитывая сказанное выше, что число п = 2* - 1 должно быть простым. Предположим, что разложение числа п на простые множители имеет вид Pj .. Рг-Все простые числаpj больше 3, так что число п нечетно и конгруэнтно (-1)-1 = -2 (по модулю 3). Из (33), (36) и (37) следует, что Ut = 0 (по модулю 2» - 1), где

t = lcm{pl-ipi+€i), ...,р/-{Рг + ег)), и каждое ej равно ±1. Отсюда получаем, что t кратно т - 2*~i. Пусть по = Щ=1 Pj~{Pj+£j); тогда по < Щ=1 Pj~{Pj + Рз) = (§)"• Кроме того, поскольку Pj + tj-четное число, то i < по/2"", ибо всякий раз, когда берется наименьшее общее кратное двух четных чисел, множитель 2 теряется. Объединяя эти результаты, получаем m < * 2()п < 4()т < Зт; отсюда, г < 2 и * = m или * = 2т, т. е. t равно степени 2. Поэтому ei = 1, вг = 1 и, если п - не простое число, должно быть п = 2 - 1 = (2* + 1)(2 - 1), где 2* + 1 и 2 - 1 -простые числа. Последнее разложение при нечетном q невозможно, поэтому п - простое.

Обратно, предположим, что п = 2« - 1-простое число. Необходимо показать, что V2<i-2 = О (по модулю п). Для этого достаточно доказать, что Vii-i = -2

(по модулю П), поскольку 24-1 = {2"-) ~ 2- Но

V2.-. = ((>/2 + >/б)/2)"+ + ((>/2 - >/б)/2)"+

Так как п - нечетное простое число, биномиальный коэффициент

{ 2к ) {2k) (2Jk-l) делится на п за исключением случая, когда 2А; = 0и2А; = п + 1. Следовательно,

2(n-l)/2 у J з(п+1)/2 (по модулю П).

Здесь 2 = (2(«+)/2)2, поэтому согласно теореме Ферма

2(п-1)/2 (2(9+1)/2)("-1) = 1.

В итоге в силу одного простого случая закона взаимности квадратичных вычетов (упр. 23) З""/ = -1, поскольку nmod3 = 1 и nmod4 = 3. Это означает, что 21-1 = -2 и, следовательно, должно быть V21-2 = О, что и требуется.

В 1460 году анонимный автор, работы которого в настоящее время хранятся в итальянских библиотеках, открыл, что числа 2 - 1 и 2 - 1 являются простыми [см. Е. Picutti, Historia. Math. 16 (1989), 123-136]. С тех пор наибольшими из известных простых чисел почти всегда оказываются числа Мерсенна. Но положение может измениться, поскольку находить простые числа Мерсенна становится все труднее, и поэтому в упр. 27 представлен эффективный способ проверки чисел другого вида.

УПРАЖНЕНИЯ

1. [10] Если последовательность пробных делителей в алгоритме А do, di, d2, ... содержит число, не являющееся простым, то почему оно никогда не появится на выходе?

2. [15] Можно ли исключить из алгоритма А шаг А2, если известно, что исходное число Л для алгоритма А не меньше 3?

3. [М20] Покажите, что существует число Р со следующим свойством: если 1 ООО < п < 1 ООО ООО, то число п будет простым тогда и только тогда, когда gcd(n, Р) = 1.

4. [М29] Используя обозначения упр. 3.1-7 и раздела 1.2.11.3, докажите, что среднее значение наименьших п, таких, что Хп - A<(„) i, находится в интервале между 1.5(тп) - 0.5 и r.625Q(m) - 0.5.

5. [21] При помощи метода Ферма (алгоритм D) найдите вручную множители числа 11111 по модулям 3, 5, 7, 8 и И.

6. [М24] Докажите, что если р - нечетное простое число и Л не кратно числу р, то количество целых чисел х, принадлежащих интервалу О < х < р, для которых существует решение у уравнения х - N = у (по модулю р), равно (р ± 1)/2.