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

$
казать очень коротко. В равенство

КВАНT 2000/?4

где g x многочлен (неполное частное), а r число (остаток), можно подставить вместо x число a. Получим
f a = a - a g a + r = r.

bg

f x = x - a g x + r,

bg b

gbg

bg b

gbg

многочлена f x , то f x = = x - a1 x - a2 ... x - am g x , где g некоторый многочлен. Применив это соображение к многочлену x p -1 - 1 , получим замечательную переформулировку малой теоремы Ферма:

c

hc

bg hc

bg hbg

a, b, c 289 и a

1000

+b

3000

+c

9000

кратно

17?

Сумма значений функции Эйлера

Значит, остаток r от деления f x на x a равен f a . Это и есть теорема Безу. А для остальных читателей теорему Безу можно сформулировать и доказать чуть более длинным, но не менее естественным способом. Теорема 5. Число a является корнем многочлена f(x) в том и только том случае, когда f(x) делится на x a, т.е. когда

bg

bg

x

p -1

-1 x -1 x - 2 K x - p +1 ,

b

gb

gb

g

где знак сравнения означает, что если раскрыть все скобки в правой части и вычесть из нее левую, то получим многочлен, коэффициенты которого кратны p. Как вы помните, для частных случаев p = 2, 3, 5, 7 и 11 это разложение на множители встречалось в первой части статьи.
Упражнение 49. Подставив x = 0, докажите теорему Вильсона: p - 1 ! -1 mod p для любого простого числа p.

Рассмотрим 100 дробей: 1/100, 2/100, ..., 100/100. Если каждую из них привести к несократимому виду, то получим 100 = 40 дробей со знаменателем 100, 50 = 20 дробей со знаменателем 50, и так далее: для каждого делителя d числа 100 получим d дробей со знаменателем d. (Почему? Потому что d это количество несократимых правильных дробей со знаменателем d.) Мы получили замечательное равенство:

bg

bg

bg

bg

b

g

b

g

100 = 100 + 50 + 25 + 20 +

f(x) = (x a)g(x), где g некоторый многочлен. Доказательство. Если
f x = x-a g x ,

Сравнение x k 1 mod p

bg b gbg то f b ag = b a - a g gb ag = 0 . Обратно, пусть f b ag = 0 . Подставим в многочлен f b xg = k x + k x + K
n n n -1 n -1

Если k делитель числа p 1, т.е. p 1 = km, то
x
p -1 k

b

g

+

b g bg bg bg b10g + b5g + b4g + b2g + b1g .

2

-1 =

= x -1 x

e

je

k m -1

bg

+x

k m -2

b

g

+ K+ x + 1 .

k

j

... + k2 x 2 + k1 x + k0 число a. Получим
0 = f a = kn a + kn -1a

bg

n

n -1

+K
2

... +k2 a + k1a + k0 . Следовательно,
f x =f x -f a =
n n n n -1 2

bg bg bg = k ex - a j + k ex - a j + K ... +k e x - a j + k b x - ag
n -1 2 n -1 2 1

Значит, многочлен x - 1 является p -1 делителем многочлена x - 1 . Поp -1 скольку x - 1 разлагается в произведение многочленов первой стеk пени, то его делитель x - 1 является произведением k многочленов первой степени. Немного подумав, можно сообразить, что мы доказали следующее утверждение. Теорема 6. Если p простое число, k делитель числа p 1, то k сравнению x 1 (mod p) удовлетворяют ровно k классов вычетов по модулю p.
Упражнения 50. Решите сравнения а) x 4 1 mod 13 ; б) x1604 1 mod 17 . (Указание. 2 и 3 первообразные корни, соответственно, по модулю 13 и по модулю 17.) 51. Зная, что 2 первообразный корень по модулю 29, решите сравнение

k

Если бы мы рассмотрели не дроби со знаменателем 100, а дроби со знаменателем n, то точно так же доказали бы следующее утверждение. Теорема 7. Для любого натурального числа n сумма значений функции Эйлера (d) по всем делителям d числа n равна n.
Упражнения 54. Если d делитель числа n, то сушествует ровно n d таких натуральных чисел k , что k n и НОД k, n = d . Докажите это. 55. Пусть n > 1. Найдите сумму всех несократимых правильных дробей, знаменатели которых равны n.

bg

bg

Доказательство теоремы 4

.

Каждая из разностей x a,

b

g

b

g

2 2 x -a = x-a x+a , ...

b

gb

g

xn - an =

= x - a xn-1 + xn-2a + K+ xan-2 + an

b

кратна x a. Теорема доказана.
Переформулировка малой теоремы Ферма

ge

-1

j

x + x + x + x + x + x + 1 0 mod 29 .
6 5 4 3 2

b

g

Из теоремы Безу следует, что если a1 , a2 , ..., am различные корни

52. Пусть p простое число. При k k k каких k сумма 1 + 2 + K + p - 1 кратна p? 53. а) Сколько существует таких пар (a,b) натуральных чисел, что a, b 1717 и a 8 + b 8 кратно 17? б) Сколько существует таких троек ( a,b,с ) натуральных чисел, что

b

g

Мы должны доказать, что если k делитель числа p 1, то среди ненулевых классов вычетов по простому модулю p существует ровно k классов порядка k. Применим индукцию. База. Для k = 1 утверждение верно. Переход. Рассмотрим некоторый делитель k числа p 1. Предположим, что для любого делителя d числа k, где d < k, существует ровно d классов вычетов порядка d. Найдем количество классов вычетов порядка k. В силу теоремы 6, сравнению k x 1 mod p удовлетворяют ровно k классов вычетов. Каждое решение x этого сравнения имеет некоторый

bg

bg

b

g

2 Для Фомы неверующего: 40 + 20 + + 20 + 8 + 4 + 4 + 2 + 1 + 1 = 100.