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

МАЛАЯ

ТЕОРЕМА

ФЕРМА

13

таблице Подумав в тех и числом n Давайте

5 первая, пятая, седьмая и одиннадцатая. немного, можно понять, что нули присутствуют только тех строках, номера которых имеют с общий делитель, отличный от 1 (докажите это!). же вычеркнем из таблицы все такие строки и
Таблица 7

б) Сумма квадратов трех целых чисел кратна 7 в том и только том случае, когда сумма четвертых степеней этих чисел кратна 7. Докажите это. 30. 31. 32. n> 7 кратно 10. Докажите, что число 7 9999 Каковы три последние цифры числа 7 ? Если целое число a взаимно просто с натуральным числом 1, то сравнение ax b mod n равносильно сравнению
r1
7 7 7 7 7 7 7 7

Ч
Таблица 6
1 5 7 11

1 1 5 7 11

5 5 1 11 7

7 7 11 1 5

11 11 7 5 1

Ч
1 3

1 1 3

3 3 1

x a b mod n . Докажите это. n! 33. Если n нечетное натуральное число, то 2 1 кратно n. Докажите это. 34*. Найдите все натуральные n > 1, для которых сумма n n n 1 + 2 + ... + n - 1 кратна n. 35*. Для каждого натурального числа s существует кратное ему натуральное число n, сумма цифр которого равна s. Докажите это.

b

g

b

g

b

g

столбцы. (Если n простое число, то вычеркивать ничего не придется.) При n = 4 получим таблицу из двух строк и столбцов (табл.6), а при n = 12 останется таблица размером 4 Ч 4 (табл.7).
Упражнение 27. Заметьте, что каждая из таблиц 27 симметрична относительно обеих своих диагоналей. Докажите, что это так для любого n.

Функция Эйлера
В 1763 году Леонард Эйлер (17071783) ввел обозначение n (читают: фи от эн) для количества r остатков, взаимно простых с n. Например, 1 = 1, 4 = 2, 12 = = 4. Если число p простое, то p = p 1. Легко вычислить m и p , где m натуральное число. В самом деле, m выпишем все p возможных остатков: 0, 1, 2, ..., p m 1. Из них кратны p в точности остатки 0, p, 2p,..., p m p. Значит, 1 m m m -1 m p =p -p = p 1- . p

bg

Теорема Эйлера
Чтобы обобщить малую теорему Ферма на случай составного числа n, оставим в таблице умножения только те строки и столбцы, в которых нет нулей, т.е. рассмотрим взаимно простые с n остатки от деления на n. В новой таблице строки (и столбцы) отличаются друг от друга лишь порядком, в котором расположены числа. Другими словами, если мы для натурального числа n выпишем все остатки a1 , a2 , ..., ar , взаимно простые с n, и домножим каждый из них на взаимно простое с n число k, то получим числа ka1 , ka2 ,..., kar , которые тоже взаимно просты с n и дают разные остатки при делении на n (докажите!). Итак, строка остатков от деления на n чисел ka1 , ka2 ,... ..., kar может отличаться от строки a1 , a2 , ..., ar только порядком расположения чисел. Поэтому точно так же, как для простого p, для составного n имеем:

ej

bg

bg

bg

bg

ej

Давайте вычислим 1000 количество чисел первой тысячи, которые не кратны ни 2, ни 5. Для этого из 1000 вычтем сначала 500 именно столько в первой тысяче четных чисел. Не забудем вычесть и 200 столько в первой тысяче чисел, кратных 5. Что еще? Еще мы должны учесть, что некоторые числа (оканчивающиеся цифрой 0) кратны и 2, и 5. Таких чисел 100 штук; каждое из них мы учитывали оба раза, а надо было только один раз! Поэтому правильный ответ дает формула

b

g

F GH

I JK

1000 = 1000 500 200 + 100 = 400.
Упражнения
ab 36. Найдите 2 5 , где a, b натуральные числа. 37. Пусть p, q различные простые числа. Найдите а) pq , ab б) p q , где a, b натуральные числа.

b

g

ka1ka2 K kar a1a2 K ar mod n ,
откуда

b

g

Значит, ar кратно n. Посколь12 r ку числа a1 , a2 , ..., ar взаимно просты с n, то k 1 кратно n. Если n простое число, то r = n 1 и получаем в точности утверждение малой теоремы Ферма. В общем же случае приходим к теореме Эйлера: Теорема 2. Если k целое число, взаимно простое с r натуральным числом n, то k 1 кратно n, где r количество взаимно простых с n натуральных чисел, не превосходящих n.
Упражнения 28. Докажите, что если число k не кратно 3, то а) k 3 при делении на 9 дает остаток 1 или 8; б) k 81 при делении на 243 дает остаток 1 или 242. 3 3 3 29. а) Если a + b + c кратно 9, то хотя бы одно из целых чисел a, b, c кратно 3. Докажите это.
4 Квант ? 1

ek - 1ja a K a 0 b произведение ek - 1ja a K
r 12 r r

mod n .

g

38. Решите уравнения: а) 7

FH

IK

di

bg

FH IK
x

= 294; б) 3 5

FH

x

y

IK

= 360.

В принципе, примененный нами способ позволяет вычислить n для любого натурального числа n. Например, чтобы вычислить 300 , мы можем выписать все числа от 1 до 300 и вычеркнуть 150 четных чисел, а также 100 чисел, кратных 3, и 60 чисел, кратных 5. Затем мы должны вспомнить, что некоторые числа вычеркнуты дважды (а иные даже трижды), и 'восстановить справедливость', т.е. к числу 300 150 100 60 прибавить 50 чисел, кратных 2 3 = 6, а также 30 чисел, кратных 2 5 = = 10, и 20 чисел, кратных 3 5 = 15. Но и этого недостаточно: каждое из десяти чисел, кратных 2 3 5 = = 30, было сначала трижды выброшено (как кратное 2, 3, 5) и затем трижды возвращено (как кратное 6, 10, 15). Но выбросить эти 10 чисел все-таки надо! Поэтому

bg

bg

300 = 300 - 150 - 100 - 60 + 50 + 30 + 20 - 10 = 80 .

bg