и таких решений не более чем П.Д" ~ 1)> поскольку число ni взаимно просто с п - 1. Если некоторое Ci > 1, то ni - 1 < nj и, следовательно, число решений не превышает п; в этом случае Ьп < п < \{п - 1), ибо п > 9.

В связи с этим можно положить, что число п равно произведению ni.,. Пг различных простых чисел. Пусть ni = 1+2qi, где fei < • • < fer. Отсюда получаем gcd(n - 1, ni - 1) = 2iqi, где fe- = min(fe,fci) и = gcd(q,qi). При модуле ni количество таких x, для которых выполняется условие ж = 1, равно qJ, а количество чисел х, для которых х = -1, равно 2qi при О < j < fej и О в противном случае. Поскольку fe > fei, то

bn=qi...qr{l+EQ<j<kx2n-

Для завершения доказательства достаточно показать, что Ьп < jgi... дгЗ*"*" = <(п), так как ip(n) < п - 1. Отсюда получаем

(1 + Eo<j<ki 2>)/2*>+-+=- < (1 + Ео<,<., 2/2"

= IjiX - 1) + {2 - 2)1{2\Г - 1)) < 112-\

Следовательно, если не выполняются равенства г = 2 и fei = fez, получаем результат. Для г = 2 в упр. 9 показано, что число п - 1 не кратно как числу п\ - 1, так и числу пг - 1. Значит, если fei = fez, то нельзя получить равенства - q\ и = 92; отсюда следует, что в этом случае qiga < 39192 и Ь„ < \{п).

\См. J. Number Theory 12 (1980), 128-138.] Из этого доказательства следует, что число Рп близко к \ только в двух случаях: когда число п равно (1 + 2qi)(l + 4qi) и когда оно является числом Кармайкла специального вида (1 + 2qi)(l + 2q2)(l + Здз). Например, для п = 49939 99877 получаем Ь„ = (49938 • 99876) и р„ « .24999; если п = 1667 • 2143 • 4523, то 6п = I(1 666 • 2 142 • 4522), р„ « .24968. Дополнительные примечания приведены в ответе к следующему упражнению.

23. (а) Доказательства для всех случаев, кроме, может быть, случая закона обратимости, выполняются просто. Пусть р = pi... Ра и q = qi... qr, где все pi и qj -простые числа. Тогда

(f) - n(fj) = П(-1)-- (fj) = (-1)--.>--"-- (J),

так что остается-только убедиться в том, что Eij (Р ~ ~ 1)/4 = (р - 1)(9 - 1)/4 (по модулю 2). Но Eij {Pi - l)(9j - 1)/4 = (Ei(P< - 1)/2)(Е;(* " 1)/2) будет нечетной тогда и только тогда, когда для нечетного количества чисел pi и qj выполняется = 3 (по модулю 4), а это происходит тогда и только тогда, когда число (р - l)(q- 1)/4 нечетно. [С. G. J. Jacobi, Bericht Konigl. PreuB. Akad. Wiss. Berlin 2 (1837), 127-136; B. A. Лебег (V. A. Lebesgue) в J. Math. Pures Appl. 12 (1847), 497-520, исследовал действенность этого метода.]

(b) Так же, как и в упр. 22, можно положить, что п = ni... Пг, где все ni = l + 2°*qi - различные простые числа и fei < • • • < fe; положим также, что gcd(n - 1, ni - 1) = 2qi. Будем называть число х плохим, если оно приводит к ошибочной классификации числа п как похожего на простое. Пусть П„ = Пг-=1 9; 2""°°~-число решений уравнения 2.(ч-1)/2 = I Количество плохих чисел х, для которых выполняется равенство () = 1, равно Пп, умноженному на дополнительный множитель при fei < fe. (Этот множитель 5 необходим, чтобы гарантировать выполнение равенства () = - 1 для четного количества чисел т при fci < fc.) Количество плохих чисел х, для которых () = -1, равно П„, если fci = fc, и О в противном случае. [Если выполняется условие х""" = -1 (по модулю ni).

то получим в результате () = -1 при ki = к, {) = +1 и кг > к и противоречие, если ki < к. Если kl = к, то существуют нечетные количества чисел кг, равных к]

Замечание. Вероятность того, что выбор плохой, будет > \ только тогда, когда п - число Кармайкла, для которого кг < к; например, п = 7 • 13 19 = 1729, число, ставшее известным благодаря Рамануджану (Ramanujan) в другом контексте. Этот анализ был продолжен Луисом Моньером (Louis Monier) при получении следующих формул в замкнутом виде для количества плохих чисел х в общем случае:

1=1 1=1

Здесь Ь„ -количество плохих чисел х в этом упражнении, а 5п равно либо 2 (если ki = к), либо (если ki < к nei является нечетным для некоторого г), либо 1 (в остальных случаях).

(с) Если ж mod п = 1, то 1 = () = () = (f). Если x = -1 (по модулю п), то порядок X по модулю т должен быть нечетным кратным числа 2-"" для всех простых делителей щ числа п. Пусть п = nJ... п*" и п, = 1 + 2qi; тогда i-) = (-l)-", так что () = +1 или -1 в зависимости от того, какой будет EiQi-четной или нечетной. Поскольку п = (1 + 2" EiO (по модулю 2), сумма J2i4i будет нечетной тогда и только тогда, когда j + 1 = к. [Theoretical Сотр. Sci. 12 (1980), 97-108.]

24. Пусть Ml - матрица, имеющая по одной строке на каждое нечетное непростое число п в интервале l<n<N,HN-l столбцов, пронумерованных от 2 до N. Значение элемента, расположенного в строке п и столбце х, равно 1, если проверка числа п алгоритмом Р посредством х дает отрицательный результат, и равно О в остальных случаях. Известно, что если N = qn + rHO<r<n, тов строке п содержится не более - 1 + q{bn + 1) + min(b„ +1,г) < q(i(n-l) + l)+min(b„ + l, г) < gn+min(in, г) = iV+min(n - г, г) < N+n < N элементов, равных 0; поэтому по меньшей мере половина элементов матрицы равна 1. Тогда в некотором столбце xi матрицы Mi хотя бы половина эле.ментов равна 1. Если вычеркнуть столбец xi и все строки, элементы которых в этом столбце равны 1, то получится матрица М2 со свойствами, подобными свойствам матрицы ЛД. Повторно выполнив описанную процедуру, можно сформировать матрицу Mr, которая имеет N - г столбцов и число строк, меньшее N/2, и которая содержит не менее 5 (Л - 1) элементов, равных 1. [См. FOCS 19 (1978), 78.]

[Подобным образом может быть доказано существование единственной бесконечной последовательности xi < Х2 < • • •, такой, что число п > 1 будет простым в том и только в том случае, если его проверка выполнена алгоритмом Р посредством х для х = xi, ..., X = Хт, где m = [lgnj([lgnj - 1). Существует ли последовательность, обладающая такими же свойствами, но в случае, когда т = O(logn)?]

25. Впервые эта теорема была строго доказана фон Мангольдтом (von Mangoldt) [Crelle 114 (1895), 255-305], который на самом деле показал, что остаточный член 0(1) равен

C-\-Jdt/i{t-l)tlnt) минус l/2fe,

при условии, что число п равно fe-й степени простого числа. Постоянная С равна li 2-1п 2 = 7 + In In 2 + En>2(ln 2)7nn! = 0.35201 65995 57547 47542 73567 67736 43656 84471+.

[Итоги исследований этой задачи за 100 лет, прошедших после публикации работы фон Мангольдта, подвел А. А. Карацуба (А. А. Karatsuba) в книге Complex Analysis in Number Theory (CRC Press, 1995). В книге Эрика Баха (Eric Bach) и Джеффри Шэллита (Jeffrey Shallit) Algorithmic Number Theory 1 (MIT Press, 1996), глава 8, проанализирована связь гипотезы Римана с конкретными задачами теории чисел.]

26. Если число N не является простым, то оно содержит простой множитель q < \/N. Согласно условиям задачи каждый простой делитель р числа / содержит целое

число Хр, такое, что порядок числа Хр по модулю q является делителем числа N - 1, но не {N - 1)/р. Поэтому, если число делит /, порядок числа Хр по модулю q будет кратным р*. В упр. 3.2.1.2-15 показано, что существует элемент х порядка / по модулю q. Однако это невозможно, поскольку тогда должно быть q > (f + 1) > (/ + 1)г > iV, и равенство не может быть выполнено. [Ргос. СятЬ. Phil. Soc. 18 (1914), 29-30.]

27. Если число к не делится на 3 и если к < 2" +1, то число fc-2" +1 будет простым тогда и только тогда, когда З = -1 (по модулю fc-2" + 1) (согласно упр. 26). Если же fc-2"+l - простое число, то согласно закону взаимности квадратичных вычетов число 3 не является квадратичным вычетом по модулю fc-2" + 1, поскольку (fc-2" + 1) mod 12 = 5. [Этот способ проверки был предложен без доказательства Протом (Proth) в Comptes Rendus Acad. Sci. Paris 87 (1878), 926.]

Чтобы применять способ проверки Прота с достаточной эффективностью, необходимо обеспечить вычисление значения a;mod(fe-2" + 1) с почти такой же скоростью, как и вычисление значения х mod (2" - 1). Положим, что х = А-2" + В; тогда х = В - [А/к\ + 2"(Amodfc), и в случае, если к представляется с однократной точностью, остаток вычисляется легко.

[Несколько сложнее проверить "простоту" чисел вида 3-2" + 1; для этого необходимо сначала применить случайные числа однократной точности, пока одно из них в соответствии с законом квадратичной взаимности не окажется квадратичным без остатка mod 3-2" -1-1. После этого в способе проверки, описанном выше, заменяем "3" этим числом. Если окажется, что nmod4 ф О, можно использовать число 5. Получается, что число 3-2" + 1 будет простым, когда п = 1,2,5,6,8,12,18, 30, 36,41,66,189, 201,209, 276,353,408, 438, 534, 2 208, 2 816, 3168, 3189, 3912, 20 909, 34 350, 42 294, 42 665, 44685, 48150, 55182, 59 973, 80190,157169, 213 321; других таких чисел вплоть до п < 300 ООО нет. Число 5-2" -Ь 1 будет простым, когда п = 1,3,7,13,15,25,39,55,75,85,127,1947,3313,4 687,5 947,13165, 23473,26607,125 413,209 787,240937 (п < 300000). См. R. М. Robinson, Ргос. Атег. Math. Soc. 9 (1958), 673-681; G. V. Cormack, Н. С. Williams, Math. Сотр. 35 (1980), 1419-1421; Н. Dubner, W. Keller, Math. Сотр. 64 (1995), 397-405; J. S. Young, Math. Сотр. 67 (1998), 1735-1738.]

28. Имеем f(p,pd) = 2/(p+ 1) + f{p,d)/p, поскольку l/(p-l- 1)-вероятность того, что число А кратно числу р; если dmodp ф О, то f{p,pd) = 1/(р + 1). Так как А - (4fe + 3)В не может быть кратно 4, то /(2,4fe--3) = 3. Так как А-(8fe-l-5)Bне может быть кратно 8, T0/(2,8fe + 5) = . /(2, 8fe + l) = i + i + l + l + i + = . Если rffP-i)/modp = (1,р-1), то соответственно для нечетных р получим f(p,d) = (2р/{р - 1), О).

29. Количество неотрицательных целых решений Xi неравенства xi Н-----\-Хт <г равно

т+г > mVr!; каждое из этих решений соответствует единственному целому числу Pi... £ [Более точньш оценки для специгшьного случая, когда числа pj являются j-ми простыми числами при всех j, приведены в работах N. G. de Bruijn, Jndag. Math. 28 (1966), 240-247; Н. Halberstam, Ргос. London Math. Soc. (3) 21 (1970), 102-107.]

30. Если Pi... p =xf (no модулю qi), можно найти такие yt, что Pi... p = (±«/i) (no модулю qf); поэтому согласно китайской теореме .об остатках находим 2** значений величины X, таких, что А =р1 ...р (по модулю N). Количество пар (ei,..., е; е/,..., е), для которых соблюдаются указанные свойства и которым соответствуют такие гюследова-тельности (ei,..., Cm), не превышает величины (,./2)- Теперь для каждого из 2 двоичных чисел а = {ai...ad)2 положим, что Па-количество показателей (ei,..., ei), таких, что (Pi •. Рт")"" = (-1)" (по модулю qi). Следовательно, доказано, что требуемое количество целых чисел X не меньше

2(Еа"а)/(,/2) Поскольку Еа - КОЛИЧеСТВО

способов замены путем перестановок не более г/2 объектов из множества т объектов, т. е. ("+/2) получаем Еа "а > {"jPfl2 > m7(2(r/2)!). [Дополнительные сведения,