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

Полная система наименьших неотрицательных вычетов: 0, 1, т -1 В приведенном выше примере: 0, 1, 2, 3, 4. Такая система вычетов составляется просто: надо выписать все не­отрицательные остатки, получающиеся при делении на m.

Полная система наименьших положительных вычетов(из каждого класса берётся наименьший положительный вычет):

1, 2, …,m. В нашем примере: 1, 2, 3, 4, 5.

3. 
   Полная система абсолютно наименьших вычетов. Вслучае нечетного m абсолютно наименьшее вычеты представляются рядом.
   

- ,…, -1, 0, 1,…, ,
а в случае четного m каким – либо из двух рядов
+1, …, -1, 0, 1,…, ,
, …, -1, 0, 1, …, .
В приведенном примере:-2, -1, 0, 1, 2.
Рассмотрим теперь основные свойства полной системы вы­четов.
Теорема 1. Любая совокупность m целых чисел:
x_l ,x₂ ,…,х_m (1)
попарно не сравнимых по модулю m, образует полную систему вы­четов по модулю m.
Доказательство.

1. 
   Каждое из чисел совокупности (1) принадлежит некоторому классу.
   
2. 
   Любые два числа x_i и x_j из (1) несравнимы между собой, т. е. принадлежат различным классам.
   
3. 
   Всего в (1) m чисел, т. е. столько же, сколько имеется клас­сов по модулю т.
   

Следовательно, совокупность чисел х₁ ,х₂ ,…,х_т — полная система вычетов по модулю m.
Теорема 2. Пусть (а, т) = 1, b — произвольное целое число; тогда если х₁ ,х₂ ,…,х_т —полная система вычетов по моду­лю m, то и совокупность чисел ах₁ + b, ах₂ + b,…, ах_m + b тоже полная система вычетов по модулю m.