Теория остатков

Теорема (Эйлер). Пусть 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, устроена следующим образом

Для дешифрования сообщения достаточно решить сравнение

При некоторых условиях на и это сравнение имеет единственное решение .

Для того, чтобы описать эти условия и объяснить, как можно найти решение, нам потребуется одна теоретико-числовая функция, так называемая функция Эйлера. Эта функция натурального аргумента обозначается и равняется количеству целых чисел на отрезке от до , взаимно простых с . Так и для любого простого числа и натурального . Кроме того, для любых натуральных взаимно простых и . Эти свойства позволяют легко вычислить значение , если известно разложение числа на простые сомножители.

Если показатель степени в сравнении (2) взаимно прост с , то сравнение (2) имеет единственное решение. Для того, чтобы найти его, определим целое число , удовлетворяющее условиям

 Скачать реферат