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

&
в) (М1510) Докажите, что существует бесконечно много таких составных чисел n -1 n -1 кратно n. n, что 3 - 2 63. Докажите, что если n составное n -1 n -1 n -1 +2 + ... + n - 1 число и 1 -1 mod n , то n число Кармайкла. (Воспользовавшись списком чисел Кар16 майкла, не превосходящих 10 , можно при помощи компьютера проверить, что не существует ни одного удовлетворяющего этому сравнению числа, не превос16 ходящего 10 . Существуют ли такие 16 числа, большие 10 , мы не знаем.) лось:

КВАНT 2000/?4

b

a +1

gb
p

- a +1

g

b

g

b

g

a + 1 - a - 1 = a - a m od p .
Упражнение 65. Если n составное, то хотя бы один из биномиальных коэффиn -2 2 k n -1 циентов Cn , Cn , ..., Cn , ..., Cn не кратен n. Докажите это.

p

p

b

g

Наиболее эффективным средством построения таких чисел сейчас является метод, основанный на следующей лемме. Лемма. Пусть q нечетное простое число, r четное натуральное, n = qr + + 1. Если существует такое целое число a, что a
n -1

1 mod n и НОД a - 1, n =

Комбинаторное доказательство
На рисунке изображены все 32 способа раскраски в два цвета круга, который разделен на 5 равных секторов. Среди

Приложения
Бином Ньютона
Малую теорему Ферма легко доказать по индукции, если использовать формулу бинома Ньютона. Мы сделаем это для натуральных чисел a, оставив случай отрицательных чисел читателю. Пусть сначала p = 3. База индукции: 13 1 = 0 делится на 3. Переход: если для некоторого числа a уже доказали, что 3 a a кратно 3, то

b

a +1

gb
3

- a +1 =
3 2

g

= a + 3a + 3a + 1 - a + 1

b

g

a 3 + 1 - a - 1 = a 3 - a 0 mod 3 .
Аналогично для p = 5: база очевидна - 1 0 mod 5 , а для перехода используем формулу

b

g

e1 b

5

b

gj

a +1

g

5

= a + 5 a + 10 a + 10 a + 5 a + 1 .
3 2

5

4

3

2

4 Видите, коэффициенты при a , a , a и a кратны 5. Поэтому

b

a +1

g

5

a + 1 mod 5 ,

5

b

g

откуда и следует возможность индукционного перехода:

b

a +1

g -b
5

a +1
5 5

g

a + 1 - a - 1 = a - a mod 5 .
Упражнение 64. Докажите индукцией по a малую теорему Ферма для а) p = 2; б) p = 7. Займемся общим случаем. Формула бинома имеет вид

b

g

них выделяются два способа когда весь круг синий и когда он весь красный. А остальные разбиты на 6 групп по 5 раскрасок, получающихся одна из другой поворотом. Задача. Сколькими способами можно раскрасить a разными красками круг, разбитый на p одинаковых секторов, где p простое число? (Каждый сектор окрашивается одной краской; не обязательно использовать все краски; две раскраски, совпадающие при повороте круга, считаются одинаковыми.) Решение. Очевидно, можно все секторы покрасить одной краской. Таких способов столько же, сколько красок, т.е. a способов. А вот из любой другой раскраски поворотами можно получить p разных раскрасок (считая и саму эту раскраску: она получается поворотом на 0њ). Значит, ответ таков:
a+ a -a p
p

= 1, то каждый простой делитель p числа n удовлетворяет сравнению p 1 mod 2q . Доказательство. Обозначим порядок числа a по модулю p буквой k. Поскольb n -1g q ку a n -1 1 mod p и a / 1 mod p , то k делится на q. В силу теоремы 3, p 1 делится на k. Следовательно, p 1 делится на q. Кроме того, p 1 четно. Лемма доказана. Следствие. Если выполнены условия леммы и r 4q + 2 , то n простое число. Доказательство. Пусть n равняется произведению не менее чем двух простых чисел. Поскольку каждое из них не меньше 2q + 1, получаем противоречие:

b

g

FH

r

IK

b

g

b

g

b

g

b

2q + 1

g

2

n = qr + 1 4 q + 2 q + 1 .

2

Покажем теперь, как, имея большое простое число q, можно пытаться строить существенно большее простое число n. Выберем случайным образом четное число r на промежутке q < r 4q + 2 и положим n = qr + 1. Затем проверим n на отсутствие малых простых делителей, перепробовав малые простые числа. 3 Если при этом выяснится, что n составное, то следует выбрать новое значение r и повторить вычисления. Если же есть надежда, что n простое, то можно случайным образом выбрать число a и проверить, выполнены ли для n -1 него соотношения a 1 mod n и
НОД a - 1, n = 1 . Если выполнены, то

.

b

a +1

g

p

= a + pa

p

p -1

+

p p -1

b

g

+

p p -1 p - 2 3!

b

gb

... +
Коэффициенты
1 2 k

g pb

2
a
p-3

a

p -2

+

p -1 2

g

+K+

a + pa + 1 .

2

C p = p , C p = p p - 1 2 , ...

... C p = p p - 1 ... p - k + 1 k ! ,... ... C
p -1 p

b

gb

b

g

Поскольку количество способов не быp вает дробным, число a - a обязано нацело делиться на p. Упражнение 66. Сколькими способами можно раскрасить a разными краска2 ми круг, разбитый а) на p секторов, где p простое число? б) на pq секторов, где p, q простые числа, p q ? (Каждый сектор окрашиваем одной краской; не обязательно использовать все краски; две раскраски, совпадающие при повороте круга, считаем одинаковыми.)

можно утверждать, что n простое (за2 метьте: n > q , так что число n записывается примерно вдвое большим количеством цифр, чем q). Если же нет, то можно взять другое значение a, и так далее. В настоящий момент нет доказательства того, что этот алгоритм сработает и тем более что он сработает достаточно быстро. Однако на практике он позволя300 ет строить большие (порядка 10 ) простые числа.

e

r

j

b

g

g

Как строят большие простые числа?
Как помнит читатель первой части статьи, для криптографической системы RSA нужны большие (лучше всего длиной в несколько сот цифр) простые числа.

=p

кратны простому числу p. Поэтому p p a + 1 a + 1 mod p , что и требова-

b

g

b

g

3 В этом месте мы чуть лукавим: следует не только делить на малые простые числа, но и применять более хитрые методы проверки на простоту. Хотя эти методы основаны на малой теореме Ферма и по сути сводятся к тому, что если для некоторого a, взаимно простого c n, n -1 число a не сравнимо с 1 по модулю n, то n составное, подробное обсуждение завело бы нас слишком далеко в бурно развивающуюся область теории чисел и вычислительной математики.