Как известно из статьи "Сравнение чисел по модулю"), всякое число 1) a сравнимо со своим вычетом r по модулю p (p положительное целое число). Следовательно число a сравнимо с одним из чисел
| 0, 1, 2, 3, ..., p−1 |
и, притом, только с одним, потому что в противном случае между этими числами нашлось бы по крайней мере два числа, сравнимых по модулю p, что невозможно (Свойство 2 статья "Сравнение чисел по модулю").
Разделим все числа на классы, относя к одному классу все те числа, которые сравнимы между собой по модулю p. Число таких классов равно p. Один из классов содержит числа сравнимые с 0 по mod p, т.е. все числа кратные p, другой − все числа сравнимые с 1 по mod p и т.д.
Возьмем по одному числу от каждого из этих классов. Тогда образуется система p чисел, имеющая то свойство, что каждое число сравнимо только с одним из этих p чисел по модулю p.
В качестве такой системы можно взять
| 0, 1, 2, 3, ..., p−1 |
или
| 1, 2, 3, ..., p |
или же любые последовательные p числа.
Данная система называется полною системою чисел, не сравнимых по модулю p или же полною системою вычетов по модулю p. Очевидно, что всякие p последовательных чисел образуют такую систему.
Все числа, принадлежащих к одному классу, имеют много общих свойств, следовательно по отношению к модулю их можно рассматривать как одно число. Каждое число, входящее в сравнение как слагаемое или множитель, может быть заменено, без нарушения сравнения, числом, сравнимым с ним, т.е. с числом, принадлежащим к одному и тому же классу.
Другой элемент, который является общим для всех чисел данного класса, является наибольший общий делитель каждого элемента этого класса и модуля p.
Пусть a и b сравнимы по модулю p, тогда
| a−b=sp |
или
| a=b+sp, |
где s некоторое целое число. Тогда каждый делитель a и b должны быть делителями чисел b и p и обратно. Следовательно исходя из наибольшего общего делителя, эти классы можно разделить на группы, и т.к. числа
| 1, 2, 3, ..., p |
образуют полную систему чисел, не сравнимых по модулю p, то число классов, члены которых имеют с модулем p наибольший общий делитель λ (p=nλ) равно φ(n). В частном случае, при λ=1 число соответствующих классов равно φ(p) (см. статью "Функция Эйлера").
Теорема 1. Если в ax+b вместо x подставим последовательно все p членов полной системы чисел
| 1, 2, 3, ..., p |
не сравнимых по модулю p, то при a и p взаимно простых чисел получим опять полную систему чисел, не сравнимых по модулю p.
Действительно. Если
| ax+b≡ay+b mod (p) |
то
| ax≡ay mod (p), |
но, т.к. a и p взаимно простые числа, то
| x≡y mod (p), |
Поэтому все числа ax+b, где x=1,2,...p-1 не сравнимы по модулю p (в противном случае, числа 1,2,...p-1 были бы сравнимы по модулю p.
1) В данной статье под словом число будем понимать целое число.