Полная система вычетов
Как известно из статьи «Сравнение чисел по модулю»), всякое число 1) 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) В данной статье под словом число будем понимать целое число.
Литература
- 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
следует что
)
Свойства:
-
Сравнение по
модулю m является отношением
эквивалентности
на множестве
,
т.е.-
(рефлексивность)
-
=>
(симметричность) -
,
=>
(транзитивность)
(доказывается из a=b+mt)
-
-
Сравнение по
модулю m является конгруэнтностью
на множестве
,
т.е. отношением эквивалентности с двумя
дополнительными условиями-
,
=>
-
,
=>
-
-
Обе части сравнения
можно поделить на их общий делитель,
если этот общий делитель взаимно прост
с модулем
Д-во:
,
=>
=>
=>
=>
-
Обе части сравнения
можно умножить на одно и тоже число
Д-во:
=>
=>
=>
=>
-
Обе части сравнения
и модуль можно умножить на одно и тоже
число
Д-во: Из
следует
-
Обе части сравнения
и модуль можно поделить на их общий
делитель
Д-во: Пусть
Имеем
-
Если сравнение
имеет место по модулю m, то оно имеет
место по модулю – делителю числа m.
Д-во: Из
следует,
что разность а-b
должна делиться на m,
поэтому она должна делиться и на любой
делитель d
числа m
-
Если сравнение
имеет место по нескольким модулям, то
оно имеет место по модулю равному НОК
этих модулей.
=>
Д-во: Из
следует,
что разностьa-b
делится на все модули
Поэтому
разность должна делиться и на НОКm
этих модулей
-
Если одна часть
сравнения и модуль делятся на некоторое
число, то и другая часть сравнения
делится на это же число
Д-во: Пусть
,
,
=>
=>
=>
=>
=>
-
Обе части сравнения
имеют с модулем один и тот же НОД.
=>
(по свойству НОД)
Соседние файлы в папке Итог
- #
- #
- #
- #
- #
- #
- #
Содержание
- 1 Сравнения по модулю
- 2 Арифметика сравнений
- 2.1 Свойства сравнений
- 3 Полная и приведенная система вычетов
- 4 Решение линейных систем по модулю
- 4.1 Примеры решения
Сравнения по модулю
Будем рассматривать целые числа в связи с остатками от деления их на данное целое число m, которое назовем модулем.
Каждому целому числу отвечает определенный остаток от деления его на m. Если двум целым a и b отвечает один и тот же остаток r, то они называются сравнимыми по модулю m.
Сравнимость для a и b записывается так :
Сравнимость чисел a и b по модулю m равносильна:
- а. Возможности представить a в форме , где t — целое.
- б. Делимости на m.
- Действительно, из следует , откуда , и , где .
- Обратно, из , представляя b в форме , выводим , где , значит .
Арифметика сравнений
Свойства сравнений
- 1. Два числа, сравнимые с третьим сравнимы между собой.
- Легко выводится из пункта «а».
- 2. Сравнения можно почленно складывать.
- Представляем сравнения, как в пункте «а» и складываем.
- 3. Сравнения можно почленно перемножать.
- Представляем сравнения, как в пункте «а», перемножаем, получим , где N—целое.
- 4. Обе части сравнения можно разделить на их общий делитель, если последний взаимно прост с модулем.
- Действительно, из , следует, что , поэтому .
- 5. Обе части сравнения можно умножить на одно и тоже число.
- Действительно, из , следует , и, следовательно, .
- 6. Обе части сравнения и модуль можно разделить на их общий делитель.
- Действительно, пусть , отсюда , и, следовательно, .
- 7. Если сравнение имеет место по нескольким модулям, то оно имеет место и по модулю равному НОК этих модулей.
- В самом деле, из следует, что разность делится на все модули . Поэтому она должна делиться и на их НОК.
- 8. Если сравнение имеет место по модулю m, то оно имеет место и по модулю d, равному любому делителю числа m.
- Следует из пункта «б».
- 9. Если одна часть сравнения и модуль делятся на некоторое число, то и другая сторона сравнения должна делиться на это число.
- Следует из пункта «а».
- 10. Если , то .
- Следует из пункта «а» по свойству НОДа.
Полная и приведенная система вычетов
Числа равноостаточные(сравнимые по модулю m) образуют класс чисел по модулю m.
Из такого определения следует, что всем числам класса отвечает один остаток r, и мы получим все числа класса,
если в форме заставим t пробегать все целые числа. Таким образом для каждого значения остатка имеется свой класс чисел.
Любое число класса называется вычетом по модулю m. Вычет получаемый при , равный самому остатку r,
называется наименьшим неотрицательным вычетом.
Любые m чисел, попарно несравнимые по модулю m, образуют полную систему вычетов по этому модулю.
Согласно 10 свойству сравнений, числа одного класса по модулю m имеют одинаковый НОД. Особенно важны классы, содержащие числа, взаимно простые с модулем. Взяв вычет от каждого такого класса, получим приведенную систему вычетов по модулю m.
Решение линейных систем по модулю
Пусть . Сравнение невозможно, если b не делится на d. При b, кратном d, сравнение имеет d решений.
Поиск решений:
,
Составим новое сравнение ,
обозначим его . Пусть его решением будет , тогда остальные решения найдутся по следующей формуле: (следует понимать, что вычет по модулю, поэтому в этой формуле можно сменить знак, для удобства), всего решений будет d. Если нахождение не является очевидным, то следует воспользоваться теорией цепных дробей, и тогда , где — числитель подходящей дроби.
Примеры решения
Пример 1.
Найдем НОД
Перейдем к новому сравнению
Легко находится
Тогда ответом будет
Пример 2.
Найдем НОД , 75 кратно 3, значит имеем 3 решения
Перейдем к новому сравнению
Воспользуемся цепными дробями, в нашем случае , значит
Тогда ответом будет .