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

МАЛАЯ

ТЕОРЕМА

ФЕРМА

17
кратно n и n > 1, поголовно делятся на 3? Подумав несколько недель, мы поняли: надо рассмотреть наименьший простой делитель p числа n. Тогда
2 -1 mod p .
n

b

Значит, 22 n 1 mod p , и поэтому порядок числа 2 по модулю p является делителем числа 2n. Поскольку он не превосходит p 1 и поскольку число n не имеет простых делителей, меньших p, есть единственная возможность: порядок числа 2 по модулю p равен 2 . Это значит, что 22 1 mod p , т. е. p = 3, что и требовалось доказать.

b

g

g

b

g

Результаты работы этой программы таковы: 2n + 1 делится на n при n = 1, 3, 9, 27, 81, 171 9 , 243, 513, 729, 1539, 2187, 3249, 4617, 6561, 9747, 13203 10 , 13851, 19683, 29241, 39609, 41553, 59049, 61731, 87723, 97641, 118827, 124659, ... Все эти числа (кроме единицы, но она не в счет) делятся на 3. И среди них присутствуют все степени тройки. Как это объяснить? Со степенями тройки мы разобрались мгновенно: по k k +1 индукции легко доказать, что 2 3 + 1 делится на 3 . И мы сразу сообразили, что верно следующее утверждение: если n кратно 3 и 2n + 1 кратно n, то 23n + 1 кратно 3n. В самом деле,

2

3n

+ 1 = 2n + 1

e

первый множитель кратен n, а второй кратен 3. (Почему? Потому что из условия 2n -1 mod n имеем 2n 2 2 1 ( m o d 3),откуда 2n - 2n + 1 -1 - -1 + 1 0 mod 3 .) Но это все не отвечало на самый наивный и самый интересный вопрос: почему числа n, для которых 2n + 1

jFH e2 j
n

2

- 2n + 1 ;

I K

b

g

di

b

bg bg

g

Упражнения 38. Пусть a, n натуральные числа, n > 1. Докажите, что если a n + 1 делится на n, то наименьший простой делитель числа n является делителем числа a + 1. 39. Пусть n натуральное n число, n > 3 и 2 + 1 кратно n. Докажите, что а) n кратно 9; б) если n > 9, то n кратно 27 или 19; в) если n делится на простое число p 3 , то p 19 ; г*) если n делится на простое число p, причем p 3 и p 19 , то p 163 . a b 40. Если 2 + 1 кратно b и 2 + 1 кратно a, где a > 1 и b > 1, то a и b кратны 3. Докажите это. 41 (М1260*). Найдите все такие натуральные n, для которых n 2 2 + 1 кратно n . n 42. а) Если 2 - 1 кратно n, то n = 1. Докажите это. б) Докажите, что существует бесконечно много натуральных n чисел n, для которых НОД 2 - 1, n > 1. в) Пусть a натуральное число, a > 2. Докажите, что n множество натуральных чисел n, для которых a - 1 кратно n, бесконечно. 43. Пусть a натуральное число, a > 1. n а) Существует бесконечно много n таких, что a + 1 делится на n. Докажите это. n б) При каких a существует число n > 1 такое, что a + 1 2 делится на n ?

e

j

(Окончание следует)

9 Заметьте: предыдущие числа степени тройки, а 171 = =19 9. 10 Впервые возник отличный от 3 и 19 простой множитель: 13203 = 163 81.
5 Квант ? 3