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

Как известно из статьи "Сравнение чисел по модулю"), всякое число 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) В данной статье под словом число будем понимать целое число.

Литература

  • 1. К.Айрленд, М.Роузен. Классическое введение в современную теорию чисел.− М:Мир, 1987.
  • 2. Г.Дэвенпорт. Высшая арифметика.− М:Наука, 1965.
  • 3. П.Г. Лежен Дирихле. Лекции по теории чисел. − Москва, 1936.