Документ взят из кэша поисковой машины. Адрес оригинального документа : http://kvant.mccme.ru/pdf/2000/04/17.pdf Дата изменения: Fri Dec 23 19:25:55 2005 Дата индексирования: Tue Oct 2 00:09:55 2012 Кодировка: Windows-1251 Поисковые слова: эта киля

МАЛАЯ

ТЕОРЕМА

ФЕРМА

%
В 1994 году в журнале Annals of Mathematics (т. 139, c. 703722) три математика Альфорд, Гренвилль и Померанц опубликовали (абсолютно недоступное для школьника) доказательство бесконечности множества чисел Кармайкла.
Упражнение 60. а) Докажите, что - a кратно числу 561 при любом целом a. б) Докажите при n = 1105 сравнения n -1 n -1 1 3 mod n . (Можно доказать, 2 что число 1105 наименьшее составное число с таким свойством.)
a
561

порядок по модулю p, причем этот порядок делитель числа k. Осталось вспомнить теорему 7 и становится ясно, что классов порядка k существует ровно k штук. Теорема 4 доказана.

bg

ется k-й степенью, то отношение количества g n простых чисел, не превосходящих n, по модулю которых g является первообразным корнем, к количеству n всех простых чисел, не превосходящих n, стремится при n к зависящему только от k пределу

bg

bg

Упражнения 56. Пусть p простое число, p > 3. Найдите остаток от деления на p произведения тех из чисел 1, 2, ..., p 1, которые являются первообразными корнями по модулю p. 57. a) Если порядки чисел a и b по модулю p равны m и n соответственно, то порядок произведения ab делитель числа НОК[m, n]. Докажите это. б) Покажите, что порядок числа ab равен mn, если числа m и n взаимно просты, и не обязательно равен числу НОК[m, n], если m и n не взаимно просты. 58. а) Пусть p простое число, p > 2, p 1 = q11 q22 K qs s разложение числа p 1 в произведение степеней различных простых чисел. Пусть g1 , g2 , ..., g s такие не кратные p числа, что p -1 q gib g i 1 mod p при i = 1, 2, ..., s. / Докажите, что число g =
a a a

lim



g

n



b ng b ng

=

=

GH
k Mq

F

1-

1 q -1

I F JK GGH
k не M q

1-

q

I bq - 1g JJK
1

,

где первое произведение распространено на все простые числа q, являющиеся делителями k, а второе на все простые числа q, не являющиеся делителями k. К настоящему времени гипотеза Артина не доказана, хотя некоторый ее аналог, относящийся к полю рациональных функций от одной переменной над конечным полем, доказать удалось.

b

g

Числа Кармайкла
В силу малой теоремы Ферма, 2 p -1 1 mod p для любого нечетного простого числа p. Существуют ли составные числа с тем же свойством? Да, существуют:

b

g

b

g

= g1

b p -1g

a q1 1

g

b p -1g

a q2 2

2

Kg

s

b p -1g

a qs s

перво-

2

340

1 mod 341 .

образный корень по модулю p. (Заметьте: мы получили еще одно доказательство существования первообразного корня по простому модулю!) б) Для любого натурального n существует взаимно простое с n целое число a, порядок которого по модулю n равен n . Докажите это. m m в) Если n = 2, 4, p или 2 p , где p нечетное простое, m натуральное, то существует первообразный корень по модулю n. Докажите это.

В самом деле, 341 = 11 31, причем 10 2 1 = 1023 = 3 11 31. (Можно проверить, что число 341 наименьшее составное число n со свойством 2 n -1 1 mod n .)

b

g

b

g

bg

Гипотеза Артина
Как мы только что доказали, для каждого простого числа p существует первообразный корень по модулю p. Интересно: какие целые числа бывают первообразными корнями, а какие не бывают? Очевидно, 1 является первообразным корнем только по модулю 2 или 3. b p -1g 2 Далее, из равенства a2 = a p -1 следует, что точный квадрат не может быть первообразным корнем ни по какому нечетному простому модулю p. Немецкий алгебраист Эмиль Артин (18981962) предположил, что для любого целого числа g -1 , не являющегося квадратом целого числа, существует бесконечно много таких простых p, что g первообразный корень по модулю p. Более того, некоторые вероятностные соображения привели Артина к следующему уточнению его гипотезы: если k есть наибольшее такое число, что g явля-

Упражнение 59. а) Если n = 4 p - 1 3 , где p простое число, p > 3, то 2n -1 1 mod n . Докажите это. б) (М672) Пусть a такое натуральa ное число, что 2 - 2 кратно a (например, a = 3). Определим последовательность x1 , x2 , x 3 , ... условиями x1 = a,

d

i

Очевидно, составное число n является числом Кармайкла тогда и только тогда, когда n 1 делится на n . Теорема 8. Составное число n = m m m = p1 1 p2 2 K ps s , где p1 , p2 , ..., ps различные простые числа, m1 , m2 , ..., ms натуральные числа, является числом Кармайкла в том и только том случае, когда m1 = = m2 = ... = ms = 1 и n 1 кратно каждому из чисел p1 1, p2 1, ... ..., ps 1. Следствие. Если n число Кармайкла, то для любого целого числа a верно сравнение an a (mod n). Доказательство теоремы 8. Пусть n число Кармайкла. Поскольку при n > 2 значение функции Кармайкла n четно, то n 1 должно быть четным. Следовательно, n нечетно. Поскольку n делится на

bg

bg

b

g

pi i = pimi -1 pi - 1 , а n 1 не делится на pi , то в случае mi > 1 получаем противоречие. Следовательно, m1 = m2 = ... = m s = 1. Завершение доказательства теоремы 8 предоставляем читателю.
Упражнения
2161038 2 mod 161038 . (При помощи ком-

ej
m

bg ch

= 2 n - 1 . Докажите, что 2 кратно x n при любом n.
x
n +1

x

xn

-2

61.

di

Но почему мы заинтересовались именно случаем a = 2? Наверное, разумнее спросить: существуют ли такие составные числа n, что для любого a, взаимно простого с n, выполнено сравнение a n 1 1 mod n ? Такие числа тоже существуют! Их называют числами Кармайкла. Наименьшее число это 561 = 3 11 17, за ним идут 1105 = 5 13 17, 1729 = 7 13 19, 2465 = 5 17 29, 2821 = 7 13 31, 6601 = 7 23 41, 8911 = 7 19 67, 10585 = 5 29 73, 15841 = 7 31 73, 29341 = 13 37 61, 41041 = 7 11 13 41,...

b

g

пьютера легко проверить, что n = = 161038 = 2 73 1103 наименьшее четное составное число, для которого n 2 2 mod n . Следующее такое четное число 215326 = 2 23 31 151.) б) Для любого целого числа a -1 существует такое четное число n > 2, что n a a mod n . Докажите это. в*) Для любого натурального числа a существует бесконечно много таких четn ных чисел n, что a a mod n . Докажите это. (Указание. Используйте теорему БиркгофаВандивера, сформулированную в упражнении 32.) m m 62. а) Пусть n = 3 - 2 . Докажите, что если n 1 кратно m, то число n -1 n -1 кратно n. -2 3 б) Существует ли составное число n, n -1 n -1 кратно n? для которого 3 - 2

b

а)

Докажите,

g

что

b

g

b

g

b

g

5 Квант ? 4