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

Пусть 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. Тогда
uu… u  rr…  r(modn)
и
uu… u arar…a r(modn).
Из этих равенств при некотором q имеем
rr…  r= a rr…  r+ nq.                                                (4)
Так как НОД(r,n)=1, i=1,…, (n), то НОД(rr…  r,n)=1. Поэтому в равенстве (4) q делится на rr…  r. Отсюда получаем                                       
1= a+nq’. 
Полученное равенство эквивалентно утверждению теоремы.
Следствие 4 (Малая теорема Ферма). Если  n - простое число, НОД(a,n)= 1, то
a 1(modn).
Следствие 5. Если НОД(a,n) = 1, то
a a(modn).
То есть, при известном значении функции  (n) обращение в кольце вычетов сводится к возведению в степень.
 В заключение приведем без доказательства полезную теорему [Massey 94].
Теорема 4. (Китайская теорема об остатках). 
Пусть  Тогда для   единственное решение  системы .