Полная система вычетов

Числа равно остаточные, или, что то же самое, сравнимые по модулю т, образуют класс чисел по модулю m.

Из такого определения следует, что всем числам класса отвечает один и тот же остаток r, и мы получим все числа класса, если в форме mq + r заставим q пробегать все целые числа.

Соответственно от различным значениям r имеем т классов чисел по модулю m.

Любое число класса называется вычетом по модулю т по отношению ко всем числам того же класса. Вычет, получаемый при q = 0, равный самому остатку r, называется наименьшим неотрицательным вычетом.

Вычет r, самый малый по абсолютной величине, называется абсолютно наименьшим вычетом.

Очевидно, при имеем r = r; при имеем r = r - m; наконец, если т четное и , то за r можно принять любое из двух чисел и .

Взяв от каждого класса по одному вычету, получим полную систему вычетов по модулю т. Чаще всего в качестве полной системы вычетов употребляют наименьшие неотрицательные вычеты 0, 1, ..., m - 1 или также абсолютно наименьшие вычеты; последние, как это следует из вышеизложенного, в случае нечетного т представляются рядом

,

а в случае четного m каким-либо из двух рядов

,

.

Теорема 1: Любые m чисел, попарно несравнимые по модулю m, образуют полную систему вычетов по этому модулю.

Доказательство: Будучи несравнимы, эти числа тем самым принадлежат к различным классам, а так как их m, т. е. столько же, сколько и классов, то в каждый класс наверно попадет по одному числу.

Теорема 2: Если (а, m) = 1 их пробегает полную систему вычетов по модулю m, то аx + b, где b - любое целое, тоже пробегает полную систему вычетов по модулю m.

Доказательство: Чисел аx + b будет столько же, сколько и чисел x, т.е. m. Согласно (Теорема 1) остается, следовательно, только показать, что любые два числа ах₁ + b и ax₂ + b, отвечающие несравнимым х₁ и x₂, будут сами несравнимы по модулю m.

Но допустив, что ax₁ + b º ax₂ + b(mod m), мы придем к сравнению ax₁ º ax₂(mod m), откуда, вследствие (a, m) = 1, получим x₁ º x₂(mod m), что противоречит предположению о несравнимости чисел х₁ и x₂. 5