Как составить полную систему вычетов

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

Как известно из статьи «Сравнение чисел по модулю»), всякое число ¹) a сравнимо со своим вычетом r по модулю p (p положительное целое число). Следовательно число a сравнимо с одним из чисел

и, притом, только с одним, потому что в противном случае между этими числами нашлось бы по крайней мере два числа, сравнимых по модулю p, что невозможно (Свойство 2 статья «Сравнение чисел по модулю»).

Разделим все числа на классы, относя к одному классу все те числа, которые сравнимы между собой по модулю p. Число таких классов равно p. Один из классов содержит числа сравнимые с 0 по mod p, т.е. все числа кратные p, другой − все числа сравнимые с 1 по mod p и т.д.

Возьмем по одному числу от каждого из этих классов. Тогда образуется система p чисел, имеющая то свойство, что каждое число сравнимо только с одним из этих p чисел по модулю p.

В качестве такой системы можно взять

или

или же любые последовательные p числа.

Данная система называется полною системою чисел, не сравнимых по модулю p или же полною системою вычетов по модулю p. Очевидно, что всякие p последовательных чисел образуют такую систему.

Все числа, принадлежащих к одному классу, имеют много общих свойств, следовательно по отношению к модулю их можно рассматривать как одно число. Каждое число, входящее в сравнение как слагаемое или множитель, может быть заменено, без нарушения сравнения, числом, сравнимым с ним, т.е. с числом, принадлежащим к одному и тому же классу.

Другой элемент, который является общим для всех чисел данного класса, является наибольший общий делитель каждого элемента этого класса и модуля p.

Пусть a и b сравнимы по модулю p, тогда

или

где s некоторое целое число. Тогда каждый делитель a и b должны быть делителями чисел b и p и обратно. Следовательно исходя из наибольшего общего делителя, эти классы можно разделить на группы, и т.к. числа

образуют полную систему чисел, не сравнимых по модулю p, то число классов, члены которых имеют с модулем p наибольший общий делитель λ (p=nλ) равно φ(n). В частном случае, при λ=1 число соответствующих классов равно φ(p) (см. статью «Функция Эйлера»).

Теорема 1. Если в ax+b вместо x подставим последовательно все p членов полной системы чисел

не сравнимых по модулю p, то при a и p взаимно простых чисел получим опять полную систему чисел, не сравнимых по модулю p.

Действительно. Если

то

но, т.к. a и p взаимно простые числа, то

Поэтому все числа ax+b, где x=1,2,…p-1 не сравнимы по модулю p (в противном случае, числа 1,2,…p-1 были бы сравнимы по модулю p.

Примечания

¹) В данной статье под словом число будем понимать целое число.

Литература

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

Опр.
Рассмотрим множество целых чисел Z
где: m
– модуль, m
– классов. Возьмем из каждого класса
по одному числу. Получим m
– чисел по одному из каждого класса.
Эти m
чисел — это полная
система вычетов.
Каждое число из класса называется
вычетом.

Полная система
наименьших неотрицательных вычетов
(ПСННВ) по модулю m
это система чисел вида: 1,2,3 … m-1.
(или ПСПНВ – полная система положительных
наименьших вычетов)Полная
система абсолютно наименьших вычетов
(ПСАНВ):

если m=2k+1,
то ПСАНВ это: -k,….., -2,-1,0,1,2,…,k.

если m=2k
то ПСАНВ любая из двух: -(k-1),…,-1,0,1,..,k
или -k,..,-1,0,1,..,k-1.

Пример:
m=10:
ПСПНВ: 0,1,2,3,4,5,6,7,8,9. ПСАНВ: -4,-3,-2,-1,0,1,2,3,4,5
или -5,-4,-3,-2,-1,0,1,2,3,4

Лемма 1:
Любые m
чисел попарно несравнимых друг с другом
образуют полную систему вычетов. Д-во:
Если m
чисел попарно несравнимы друг с другом,
то они принадлежат разным классам, а
поскольку чисел m и классов m,
то каждому классу принадлежит по одному
из этих чисел, которые вместе образуют
полную систему вычетов. ЧТД

Лемма 2: Пусть
(a,m)=1,

.
Если x
пробегает полную систему вычетов по
модулю m,
то ax+b
тоже пробегает полную систему вычетов
по модулю m.

Д-во: Пусть

тогда

достаточно показать что числа во втором
множестве попарно несравнимы по модулю
m.
От противного: пусть числа сравнимы, то
есть

по свойствам сравнения

что невозможно, так как

принадлежат разным классам, следовательно
они несравнимы. ЧТД

Опр.
По свойству сравнения все вычеты одного
класса чисел по модулю m
имеют с m
один о тот же НОД, и с каждого класса
чисел, для которых этот НОД=1 берем по
одному числу, получаем систему чисел,
которая называется приведенная
система вычетов
по модулю m.

Число чисел в
приведенной системе вычетов равно в
точности
—
(функция Эйлера – количество чисел ряда
1,2, .. m
взаимно простых с m.

,
где
)

Лемма 1:
Любые

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

Д-во:
Классов чисел, вычеты которых имеет с
m
НОД=1 в точности
.
Имеем

чисел, чей НОД с m
равен 1 и при этом они принадлежат разным
классам, то есть они образуют приведенную
систему вычетов по модулю m.
ЧТД

Лемма 2: Пусть
(a,m)=1
Если x
пробегает полную систему вычетов по
модулю m,
то ax
тоже пробегает полную систему вычетов
по модулю m.

Д-во: Пусть

тогда

достаточно показать что числа во втором
множестве попарно несравнимы по модулю
m.
От противного: пусть числа сравнимы, то
есть

по свойствам сравнения

что невозможно, так как

принадлежат разным классам, следовательно
они несравнимы. ЧТД

Сравнения,
свойства сравненийразобьем на классы
Опр.
Возьмем m>0,

,
m
– модуль. Целые числа a
и b назовем сравнимыми
по модулю
m, если они имеют равные остатки от
деление на m. Пример: m=5.,,

[0] [1] …. [m-1]
Эти классы не пересекаются, их
объединение дает

Утверждения:
следующие
3 условия равносильны:

1.

2. a-b делится на
m

3.
a=b+mt,t – целое.

Д-во: 1->2 Изследует:a=mq+r;
b=mq1+r
=> a-b=m(q-q1),
2->3 Из a-b делится на m следует a-b=tm =>
a=b+tm
3->1 Из Обратно так же (из a=b+mt
следует что
)

Свойства:

1. Сравнение по
   модулю m является отношением
   эквивалентности
   на множестве
   ,
   т.е.

   1. (рефлексивность)

   2. =>
      (симметричность)

   3. ,=>(транзитивность)
      (доказывается из a=b+mt)

2. Сравнение по
   модулю m является конгруэнтностью
   на множестве
   ,
   т.е. отношением эквивалентности с двумя
   дополнительными условиями

   1. ,
      =>

   2. ,
      =>

3. Обе части сравнения
   можно поделить на их общий делитель,
   если этот общий делитель взаимно прост
   с модулем

Д-во:
, =>

=>=>=>

1. Обе части сравнения
   можно умножить на одно и тоже число

Д-во:
=>

=>=>=>

1. Обе части сравнения
   и модуль можно умножить на одно и тоже
   число

Д-во: Из
следует

1. Обе части сравнения
   и модуль можно поделить на их общий
   делитель

Д-во: Пусть
Имеем

1. Если сравнение
   имеет место по модулю m, то оно имеет
   место по модулю – делителю числа m.

Д-во: Из
следует,
что разность а-b
должна делиться на m,
поэтому она должна делиться и на любой
делитель d
числа m

1. Если сравнение
   имеет место по нескольким модулям, то
   оно имеет место по модулю равному НОК
   этих модулей.
   =>

Д-во: Из
следует,
что разностьa-b
делится на все модули
Поэтому
разность должна делиться и на НОКm
этих модулей

1. Если одна часть
   сравнения и модуль делятся на некоторое
   число, то и другая часть сравнения
   делится на это же число

Д-во: Пусть
,,
=>

=>
=>=>=>

1. Обе части сравнения
   имеют с модулем один и тот же НОД.
   =>(по свойству НОД)

Соседние файлы в папке Итог

• #
• #
• #
• #
• #
• #
• #

Сравнения по модулю

• а. Возможности представить a в форме , где t — целое.
• б. Делимости на m.
  • Действительно, из следует , откуда , и , где .
  • Обратно, из , представляя b в форме , выводим , где , значит .

Арифметика сравнений

Свойства сравнений

• 1. Два числа, сравнимые с третьим сравнимы между собой.
  • Легко выводится из пункта «а».

• 2. Сравнения можно почленно складывать.
  • Представляем сравнения, как в пункте «а» и складываем.

• 3. Сравнения можно почленно перемножать.
  • Представляем сравнения, как в пункте «а», перемножаем, получим , где N—целое.

• 4. Обе части сравнения можно разделить на их общий делитель, если последний взаимно прост с модулем.
  • Действительно, из , следует, что , поэтому .

• 5. Обе части сравнения можно умножить на одно и тоже число.
  • Действительно, из , следует , и, следовательно, .

• 6. Обе части сравнения и модуль можно разделить на их общий делитель.
  • Действительно, пусть , отсюда , и, следовательно, .

• 7. Если сравнение имеет место по нескольким модулям, то оно имеет место и по модулю равному НОК этих модулей.
  • В самом деле, из следует, что разность делится на все модули . Поэтому она должна делиться и на их НОК.

• 8. Если сравнение имеет место по модулю m, то оно имеет место и по модулю d, равному любому делителю числа m.
  • Следует из пункта «б».

• 9. Если одна часть сравнения и модуль делятся на некоторое число, то и другая сторона сравнения должна делиться на это число.
  • Следует из пункта «а».

• 10. Если , то .
  • Следует из пункта «а» по свойству НОДа.

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

Решение линейных систем по модулю

Пусть . Сравнение невозможно, если b не делится на d. При b, кратном d, сравнение имеет d решений.
Поиск решений:
,
Составим новое сравнение ,
обозначим его . Пусть его решением будет , тогда остальные решения найдутся по следующей формуле: (следует понимать, что вычет по модулю, поэтому в этой формуле можно сменить знак, для удобства), всего решений будет d. Если нахождение не является очевидным, то следует воспользоваться теорией цепных дробей, и тогда , где — числитель подходящей дроби.

Примеры решения

Пример 1.

Найдем НОД
Перейдем к новому сравнению
Легко находится
Тогда ответом будет

Пример 2.

Найдем НОД , 75 кратно 3, значит имеем 3 решения
Перейдем к новому сравнению
Воспользуемся цепными дробями, в нашем случае , значит
Тогда ответом будет .