uzluga.ru
добавить свой файл




Основные теоремы о вычетах.


Пусть n взаимно-простое с а число, а 0; r=0, r,…,r - наименьшие неотрицательные представители различных классов вычетов mod n. Рассмотрим множество чисел:

u = (ar)(modn), u = (ar)(modn),… , u = (ar)(modn).

Лемма 1. Числа u, u,… , u - различные.

Д о к а з а т е л ь с т в о. Предположим противное. Тогда i >j:
u= u и по лемме 1 п. 4.2 ar-ar = nq, q Z. Тогда

a(r-r) = nq.

Так как n простое и взаимно простое с a, то n делит (r-r). Однако по лемме 1 п. 4.2 это противоречит тому, что r и r выбирались из разных классов вычетов. Лемма доказана.

Следствие 1. Числа u, u,… , u - наименьшие неотрицательные представители всех классов вычетов.

Следствие 2. Среди чисел u, u,… , u есть 1.

Следствие 3. Если n простое, НОД(a,n) = 1, то уравнение
ax 1(modn) имеет единственное решение с точностью до класса.

Доказательство следует из следствия 2.

Определение1. Функция Эйлера (n), nN, определяется как число натуральных чисел, меньших n и взаимно простых с n, то есть

(n)= |{a: НОД(a,n) = 1, a<n}|.

Если n простое, то (n)= n-1. Если n=pq, где p и q простые, то
(n)=(p-1)(q-1).

Пусть для nN r, r,… , r - все взаимно простые с n натуральные числа, меньшие n. Будем называть этот набор системой представителей для n. Пусть a Z и НОД(a,n) = 1. Рассмотрим набор чисел

u = (ar)(modn), u = (ar)(modn),… , u = (ar)(modn). (2)

Лемма 2. Если НОД(a,n) = 1, то набор чисел u, u,… , u является системой представителей для n.

Д о к а з а т е л ь с т в о.

Сначала докажем, что [u], [u],… , [u] -различны. Предположим противное. Тогда существуют u и u такие, что

u u(modn).

Отсюда следует ar-ar = nq при некотором q. Так как НОД(a,n) = 1, то в произведении a(r-r) сомножитель (r-r) делится на n.Это значит, что r и r лежат в одном классе вычетов по modn. Пусть r > r, тогда
r-r=n. Это противоречит тому, что 0< r-r<n. Каждое из чисел
u, u,… , u меньше n, они различные и их (n) штук. Докажем, что каждое из чисел u взаимно просто с n. Числа ar - взаимно просты с n, так как

НОД(a,n) = 1, НОД(n,r) = 1, i=1,…,(n). (3)

Тогда, если u имеет с n общий делитель d>1, то из равенства
ar = nq+ u следует, что d|ar. Это противоречит (3). Отсюда следует, что u, u,… , u - система представителей. Лемма 2 доказана.

Лемма 2 является основой для доказательства ряда важных для криптографических приложений результатов.

Теорема 1. Если nN, aZ, НОД(a,n) = 1, то уравнение ax 1(modn) имеет единственное решение в кольце вычетов по modn.

Д о к а з а т е л ь с т в о. Так как 1 принадлежит системе представителей для n, то в наборе u, u,… , u из леммы 2 найдется 1. Соответствующее r такое, что

1= u= ar(modn)

определяет искомое . Теорема доказана.

Теорема 2 (Обобщенная теорема Евклида). Для любых a и b из Z найдутся u, v из Z, такие, что

au + bv = НОД(a,b).

Д о к а з а т е л ь с т в о. Пусть сначала НОД(a,b) = 1, тогда по теореме 1 уравнение ax 1(modb) имеет единственное решение
x u(modb) в кольце вычетов по модулю b. Это означает, что при
некотором v:

au-1=bv.

Если НОД(a,b)=d, то a=ad, b=bd и НОД(a,b) = 1. Тогда для a и b найдутся u и v, что au+bv=1. Умножая обе части равенства на d, получим требуемое равенство. Теорема доказана.

Теорема 3 (Теорема Эйлера). Если nN, aZ, НОД(a,n) = 1, то

a (modn)=1.

Д о к а з а т е л ь с т в о.

Из леммы 2 следует, что если r, r,… , r - система представителей для n, то

u = (ar)(modn), u = (ar)(modn),… , u = (ar)(modn).

также система представителей для n. Тогда

uuu rrr(modn)

и

uuu arara r(modn).

Из этих равенств при некотором q имеем

rrr= a rrr+ nq. (4)

Так как НОД(r,n)=1, i=1,…, (n), то НОД(rrr,n)=1. Поэтому в равенстве (4) q делится на rrr. Отсюда получаем

1= a+nq.

Полученное равенство эквивалентно утверждению теоремы.

Следствие 4 (Малая теорема Ферма). Если n - простое число, НОД(a,n)= 1, то

a 1(modn).

Следствие 5. Если НОД(a,n) = 1, то

a a(modn).

То есть, при известном значении функции (n) обращение в кольце вычетов сводится к возведению в степень.

В заключение приведем без доказательства полезную теорему [Massey 94].

Теорема 4. (Китайская теорема об остатках).

Пусть Тогда для единственное решение системы .