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

Малая теорема Ферма
МАЛАЯ ТЕОРЕМА ФЕРМА

11

В.СЕНДЕРОВ, А.СПИВАК

ков (заново доказав малую теорему Ферма и теорему Эйлера в формулировках, которые позволят решить многие интересные задачи), о первообразных корнях, функции Кармайкла, числах Мерсенна и о многом другом. Статья насыщена интересными задачами. Вряд ли возможно при первом чтении решить их все. Но мы уверены: многие из них настолько заинтригуют вас, что рано или поздно все они будут решены самостоятельно или с помощью раздела 'Ответы, указания, решения'.

М

Ы РАССКАЖЕМ О ПЕРИОДИЧНОСТИ ОСТАТ-

Малая теорема Ферма гласит: a p a (mod p) для любого целого числа a и простого числа p. В частности, если a не кратно p, то a p-1 1 (mod p). Функция Эйлера n это количество взаимно простых с числом n и не превосходящих n натуральных чисел. Например, p = p 1 для любого простого p. В m m m первой части для n = p1 1 p2 2 K ps s , где p1 , p2 , ..., ps различные простые числа, m1 , m2 , ..., ms натуральные числа, доказана общая формула

bg bg

Напоминание
Как помнит читатель первой части статьи, числа a и b сравнимы по модулю n, если a b кратно n, т.е. a b = = kn, где k целое число.
Продолжение. Начало см. в 'Кванте' ?1

n = p1

b g e je p j = ep -
m1 m2 2 m1 1

K p p1
m1 -1

ej je p
ms s

= - p2
m2 -1

m2 2

j K e

ps s - p

m

m s -1 s

j

.

Теорема Эйлера это обобщение малой теоремы Ферма на случай составного модуля: a b n g 1 (mod n), где a целое число, взаимно простое с натуральным числом n.

3*

Иллюстрация М.Сумниной