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

МАЛАЯ
7 7 z

ТЕОРЕМА

ФЕРМА
2

15

23*. Докажите, что уравнение x + y = 1998 не имеет решений в натуральных числах. 24*. Для любого целого числа k 1 существует бесконечно n 2 много натуральных чисел n, для которых число 2 + k составное. Докажите это. (Аналогичное утверждение для k = 1 мы доказать не умеем: существует или нет бесконечно много составных чисел вида 2
2 n

База случай m = 3. Число a - 1 = (a 1)(a + 1) кратно 8, поскольку одно из соседних четных чисел a 1 и a + + 1 кратно 4. Переход. Пусть утверждение верно для некоторого m 3 . Рассмотрим разложение на множители:

+ 1 , неизвестно.)

a

2

m -1

-1 = a

FH

2

m- 2

-1 a

IK FH

2

m -2

+1 .

IK

Усиление теоремы Эйлера
Рассмотрим утверждение теоремы Эйлера при n = 360. Очевидно, 360 = 23 5 9 = 4 4 6 = 96. Значит, для любого целого числа a, взаимно простого с 360, выполнено сравнение

bgc
a
a

h

Поскольку первый множитель правой части делится на m 2 , а второй множитель четен, произведение делится на 2m +1 , что и требовалось доказать.
Упражнение 26. Пусть a нечетно, m 3 . а) Решите сравнение m m 2 2 mod 2 . б) Докажите, что сравнение x a mod 2 разрешимо для тех и только тех a, для которых a 1 mod 8 .
x a
2

96

1 mod 360 .
1 mod 360 .

А на самом деле верно даже сравнение
12

b

g

e

j

e b

g

j

b

g

Для доказательства достаточно применить теорему Эйлера к каждому из модулей 8, 5 и 9:

a 4 1 mod 8 ,
a 1 mod
4

a 6 1 mod

и заключить, что a12 1 по каждому из модулей 8, 5 и 9, а значит, и по модулю 360. В общем виде это можно сформулировать следующим образом. Рассмотрим разложение
n = p1 1 p2 2 K p
m m ms s

b b b

g 5g 9g

, ,

Через n обозначим такое наименьшее натуральное число k, что a k - 1 кратно n для любого числа a, взаимно простого с n. Функцию называют функцией Кармайкла. Легко понять, что для любого натурального числа l, не кратного n , существует такое взаимно простое с n целое l число a, что a 1 mod n . Чтобы это доказать, разделим / с остатком l на n . Имеем:

bg

Функция Кармайкла

bg

b bg

g

l = n q + r,

где q целое неотрицательное, 0 < r < n . При этом

bg

числа n в произведение степеней различных простых множителей. Обозначим через f n наименьшее общее кратное чисел pi
3

f(360)= НОК = НОК 4, 6, 4 = 12.) Тогда при любом целом a, взаимно простом с n, справедливы сравнения

ej e2 j, e3 j, b5g
mi 2

, где i = 1, 2, ..., s. (Например,

bg

a

fn

bg

1 mod pi

где i = 1, 2, ..., s; следовательно,

e

mi

j

,

a

fn

bg

1 mod n .

Упражнение 25. а) Для каких натуральных n верно равенство f(n) = n ? m б) Пусть n > 4 и n не представимо ни в виде p , ни в виде 2 p m , где p нечетное простое, m натуральное. Докажите, что невозможно так расположить все n меньших n и взаимно простых с ним натуральных чисел вдоль окружности, чтобы для 2 любых трех стоящих подряд чисел a, b, c разность b ac делилась на n. (Другими словами, для этих n нет первообразного корня, т.е. нет числа g, порядок которого по модулю n равен n .)

b

g

bg

bg

bg

Сравнения по модулю 2m

Пусть m натуральное число, m 3 . Теорема Эйлера утверждает, что a для любого нечетного 1 mod 2 числа a. На самом деле верно более сильное утверждение:
2
m -1

e

m

j

g b g 1 m od n g , a откуда для числа k = НОК b mg, bng имеем a 1 b m od m g , a 1 b mod ng , так что a 1 b mod mng . Таким образом, bmng k . Осталось доказать, что bmng делится как на bmg , так и на bn g . Сделаем это 'от противного'. Пусть, например, l = bmng не делится на bm g . Тогда существует такое число b, взаимно простое с m, что b / 1 bmod m g . Рассмотрим число a, для которого a b bmod mg и a взаимно просто с n. Очевидно, a b /1 bmod mg , что и
a
m

Поскольку r < n , хотя бы для одного взаимно простого с n числа a сравнение a r 1 mod n не выполнено. Это и требовалось доказать. Функция Кармайкла обладает еще одним интересным свойством: mn = НОК m , n для любых взаимно простых натуральных чисел m и n. В самом деле, если целое число a взаимно просто с числами m и n, то по определению

bg

al = a

e

n

bg

j

q

bg

ar .

b

g

bg

b g bg b b

bg

1 mod m ,

n

k

k

k

l

7

l

l

требовалось доказать.

a

2

m -2

1 mod 2

Его легко доказать по индукции.
4*

e

m

j

.

7 Почему такое a существует? Например, можно рассмотреть числа вида b + mx, где x = 1, 2, ..., n. Они дают разные остатки при делении на n. Поскольку этих чисел n столько же, сколько классов вычетов по модулю n, то среди них найдется и нужное нам a.