Теория остатков (стр. 6 из 10)
Лемма 3. Пусть m 1 , m 2 , ..., m k – попарно взаимно просты и m 1 m 2 ...m k =M 1 m 1 =M 2 m 2 =...=M k m k , где M j =m 1 ...m j-1 m j+1 ...m k
1) Если x 1 , x 2 , ..., x k пробегают полные системы вычетов по модулям m 1 , m 2 , ..., m k соответственно, то значения линейной формы M 1 x 1 +M 2 x 2 + ...+M k x k пробегают полную систему вычетов по модулю m=m 1 m 2 ...m k .
2) Если 1 , 2 , ..., k пробегают приведенные системы вычетов по модулям m 1 , m 2 , ..., m k соответственно, то значения линейной формы M 1 1 +M 2 2 + ...+M k k пробегают приведенную систему вычетов по модулю m=m 1 m 2 ...m k .
Доказательство.
1) Форма M 1 x 1 +M 2 x 2 + ...+M k x k принимает, очевидно, m 1 m 2 ...m k =m значений. Покажем, что эти значения попарно несравнимы. Ну пусть
M 1 x 1 +M 2 x 2 + ...+M k x k M 1 x 1 +M 2 x 2 + ...+M k x k (mod m)
Всякое M j , отличное от M s , кратно m s . Убирая слева и справа в последнем сравнении слагаемые, кратные m s , получим:
M s x s M s x s (mod m s ) x s x s (mod m s )
– противоречие с тем, что x s пробегает полную систему вычетов по модулю m s .
2). Форма M 1 1 +M 2 2 + ...+M k k принимает, очевидно, ( m 1 ) ( m 2 ) ... ( m k ) = ( m 1 m 2 ... m k )= ( m ) (функция Эйлера мультипликативна!) различных значений, которые между собой по модулю m=m 1 m 2 ...m k попарно несравнимы. Последнее легко доказывается рассуждениями, аналогичными рассуждениям, проведенным при доказательстве утверждения 1) этой леммы. Так как ( M 1 1 +M 2 2 + ...+M k k ,m s )=(M s s ,m s )=1 для каждого 1 s k , то ( M 1 1 +M 2 2 + ...+M k k ,m s )=1 , следовательно множество значений формы M 1 1 +M 2 2 + ...+M k k образует приведенную систему вычетов по модулю m .
Лемма 4. Пусть x 1 , x 2 , ..., x k ,x пробегают полные, а 1 , 2 ,..., k , – пробегают приведенные системы вычетов по модулям m 1 , m 2 , ..., m k и m=m 1 m 2 ...m k соответственно, где (m i m j )=1 при i j . Тогда дроби {x 1 /m 1 +x 2 /m 2 +...+x k /m k } совпадают с дробями {x/m} , а дроби { 1 /m 1 + 2 /m 2 +...+ k /m k } совпадают с дробями { /m} .
Доказательство. Доказательство обоих утверждений леммы 4 легко получается применением предыдущей леммы 3 после того, как вы приведете каждую сумму {x 1 /m 1 +x 2 /m 2 +...+x k /m k } и { 1 /m 1 + 2 /m 2 +...+ k /m k } к общему знаменателю:
{x 1 /m 1 +x 2 /m 2 +...+x k /m k }={(M 1 x 1 +M 2 x 2 +...+M k x k )/m} ;
{ 1 /m 1 + 2 /m 2 +...+ k /m k }={(M 1 1 +M 2 2 +...+M k k )/m} ,
где M j =m 1 ...m j-1 m j+1 ...m k .
Если теперь принять во внимание, что дробные части чисел, получающихся при делении на модуль m любых двух чисел, сравнимых по модулю m , одинаковы (они равны r/m , где r – наименьший неотрицательный вычет из данного класса), то утверждения настоящей леммы становятся очевидными.
Теорема (Эйлер). Пусть m>1 , (a,m)=1 , ( m ) – функция Эйлера. Тогда:
a ( m ) 1(mod m) .
Доказательство. Пусть х пробегает приведенную систему вычетов по mod m :
x=r 1 ,r 2 ,...,r c
где c= (m) их число, r 1 ,r 2 ,..., r c - наименьшие неотрицательные вычеты по mod m . Следовательно, наименьшие неотрицательные вычеты, соответствующие числам ax суть соответственно:
1 , 2 ,..., c
– тоже пробегают приведенную систему вычетов, но в другом порядке (см. Лемму 2 из пункта 17). Значит:
a r 1 (mod m)
a r 2 (mod m)
...
a r c (mod m)
Перемножим эти с штук сравнений. Получится:
a c r 1 r 2 ...r c j 1 j 2 ... j c (mod m)
Так как r 1 r 2 ...r c = 1 2 ... c 0 и взаимно просто с модулем m , то, поделив последнее сравнение на r 1 r 2 ...r c , получим a ( m ) 1(mod m) .
Вторая теорема этого пункта – теорема Ферма – является непосредственным следствием теоремы Эйлера (конечно, при схеме изложения материала, принятой в этой книжке).
Теорема (Ферма). Пусть р – простое число, р не делит a . Тогда:
a p-1 1(mod p) .
Доказательство 1. Положим в условии теоремы Эйлера m=p , тогда (m)=p-1 (см. пункт 14 ) . Получаем a p-1 1(mod p) .
Необходимо отметить важность условия взаимной простоты модуля и числа a в формулировках теорем Эйлера и Ферма. Простой пример: сравнение 6 2 1(mod 3) очевидно не выполняется. Однако можно легко подправить формулировку теоремы Ферма, чтобы снять ограничение взаимной простоты.
Следствие 1. Без всяких ограничений на a Z ,
a p a(mod p) .
Доказательство. Умножим обе части сравнения a p-1 1(mod p) на a . Ясно, что получится сравнение, справедливое и при a , кратном р .
Доказательство 2. Так как р - простое число, то все биномиальные коэффициенты:
(кроме C 0 p и C p p ) делятся на р , ибо числитель выписанного выражения содержит р , а знаменатель не содержит этого множителя. Если вспомнить бином Ньютона, то становится понятно, что разность (A+B) p -A p -B p =C p 1 A p-1 B 1 +C p 2 A p-2 B 2 +...+C p p-2 A 2 B p-2 +C p p-1 A 1 B p-1 , где А и В – какие угодно целые числа, всегда делится на р . Последовательным применением этого незатейливого наблюдения получаем, что (A+B+C) p -A p -B p -C p ={[(A+B)+C] p -(A+B) p -C p }+(A+B) p -A p -B p всегда делится на р ; (A+B+C+D) p -A p -B p -C p -D p всегда делится на р ; и вообще, (A+B+C+...+K) p -A p -B p -C p -...-K p всегда делится на р . Положим теперь в последнем выражении A=B=C=...=K=1 и возьмем количество этих чисел равным a . Получится, что a p -a делится на р , а это и есть теорема Ферма в более общей формулировке.
Следствие 2. (a+b) p a p +b p (mod p) .
Система шифрования RSA
и 
натуральные числа. Функция 
, реализующая схему RSA, устроена следующим образом 
Для дешифрования сообщения
достаточно решить сравнение 
При некоторых условиях на
и это сравнение имеет единственное решение 
.Для того, чтобы описать эти условия и объяснить, как можно найти решение, нам потребуется одна теоретико-числовая функция, так называемая функция Эйлера. Эта функция натурального аргумента
обозначается 
и равняется количеству целых чисел на отрезке от 
до , взаимно простых с . Так 
и 
для любого простого числа 
и натурального 
. Кроме того, 
для любых натуральных взаимно простых 
и 
. Эти свойства позволяют легко вычислить значение , если известно разложение числа на простые сомножители.