Решение сравнений и их приложения

Доказательство.
Рассмотрим
ах₁ + b, ах₂ + b,…, ах_m + b (2)

1. 
   Каждое из чисел совокупности (2) принадлежит некоторому классу.
   
2. 
   Любые два числа ax_i +b и ax_j + b из (2) несравнимы между собой, то есть принадлежат различным классам.
   

Действительно, если бы в (2) имелись такие два числа, что
ax_i +b ax_j + b (mod m), (i = j), то получили бы ax_i ax_j (mod т). Так как (а, т) = 1, то свойству сравнений можно сократить обе части сравнения на а. Получаем x_i x_j (mod m).

По условию же x_i x_j (mod т) при (i = j) , так как х₁ ,х₂, ..., х_m — полная система вычетов.

3. 
   Совокупность чисел (2) содержит т чисел, то есть столько, сколько имеется классов по модулю m.
   

Итак, ах₁ + b, ах₂ + b,…, ах_m + b — полная система выче­тов по модулю m.
Пример.
Пусть т = 10, а = 3, b = 4.
Возьмем какую-нибудь полную систему вычетов по модулю 10, например: 0, 1, 2,…, 9. Составим числа вида ах + b. Получим: 4, 7, 10, 13, 16, 19, 22, 25, 28, 31. Полученная совокупность чи­сел — полная система вычетов по модулю 10.

2. 
   Приведённая система вычетов.
   

Докажем следующую теорему.

Теорема 1.
Числа одного и того же класса вычетов по моду­лю m имеют с m один и тот же наибольший общий делитель: если a b (mod m), то (а, m) = (b, m).
Доказательство.
Пусть a b (mod m). Тогда а = b+mt, где t є z. Из этого равенства следует, что (а, т) = (b, т).
Действительно, пусть δ-общий делитель a и m, тогда a δ, m δ. Так как а = b+mt, то b=a-mt, следовательно b δ. Поэтому любой общий делитель чисел a и m является общим делителем m и b.
Обратно, если m δ и b δ, то а = b+mt делится на δ, a потому любой общий делитель m и b является общим делителем a и m. Теорема доказана.