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

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

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

Источник

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

В предыдущем пункте было отмечено, что отношение _m сравнимости по произвольному модулю m есть отношение эквивалентности на множестве целых чисел. Это отношение эквивалентности индуцирует разбиение множества целых чисел на классы эквивалентных между собой элементов, т.е. в один класс объединяются числа, дающие при делении на m одинаковые остатки. Число классов эквивалентности _m (знатоки скажут – «индекс эквивалентности _m«) в точности равно m.

Определение. Любое число из класса эквивалентности _m будем называть вычетом по модулю m. Совокупность вычетов, взятых по одному из каждого класса эквивалентности _m, называется полной системой вычетов по модулю m (в полной системе вычетов, таким образом, всего m штук чисел). Непосредственно сами остатки при делении на m называются наименьшими неотрицательными вычетами и, конечно, образуют полную систему вычетов по модулю m. Вычет ρ называется абсолютно наименьшим, если ⎪ρ⎪ наименьший среди модулей вычетов данного класса.

Пример: Пусть m = 5. Тогда:

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

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

– противоречие с тем, что x₁ и x₂ различны и взяты из полной системы вычетов.

Поскольку все числа из данного класса эквивалентности _m получаются из одного числа данного класса прибавлением числа, кратного m, то все числа из данного класса имеют с модулем m один и тот же наибольший общий делитель. По некоторым соображениям, повышенный интерес представляют те вычеты, которые имеют с модулем m наибольший общий делитель, равный единице, т.е. вычеты, которые взаимно просты с модулем.

Определение. Приведенной системой вычетов по модулю m называется совокупность всех вычетов из полной системы, взаимно простых с модулем m.

Приведенную систему обычно выбирают из наименьших неотрицательных вычетов. Ясно, что приведенная система вычетов по модулю m содержит ϕ(m) штук вычетов, где ϕ(m)– функция Эйлера – число чисел, меньших m и взаимно простых с m.

Функция Эйлера.

Функция Эйлера ϕ(a) есть количество чисел из ряда 0, 1, 2. a–1, взаимно простых с a.

Лемма.Пусть

Тогда:

Пример. Пусть m = 42. Тогда приведенная система вычетов суть:

1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41.

Лемма 2. 1) Любые ϕ(m) чисел, попарно не сравнимые по модулю m и взаимно простые с модулем, образуют приведенную систему вычетов по модулю m.

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

Доказательство. Утверждение 1) – очевидно. Докажем утверждение 2). Числа аx попарно несравнимы (это доказывается так же, как в лемме 1 этого пункта), их ровно ϕ(m) штук. Ясно также, что все они взаимно просты с модулем, ибо d(a, m)=1, d(x,m)=1 ⇒ d(ax, m)=1. Значит, числа аx образуют приведенную систему вычетов.

Здесь k=0,1. m-1 – пробегает полную систему вычетов по модулю m.

в противном случае, при а не кратном m,

Теорема 2. Пусть m>0 – целое число, ξ пробегает приведенную систему вычетов по модулю m. Тогда (сумма первообразных корней степени m):

Источник

Определение и свойства вычетов

Классы вычетов. Системы вычетов

Краткие сведения из теории

Применяя теорему о делении с остатком можно множество целых чисел разбить на ряд классов. Рассмотрим пример. Пусть m= 6. Тогда имеем шесть классов разбиения множества целых чисел по модулю 6:

r = 0;

r = 1;

r = 2;

r = 3;

r = 4;

r = 5;

где через rобозначен остаток от деления целого числа на 6.

Напомним теорему о делении с остатком:

Теорема: Разделить число на число , , с остатком, значит, найти пару целых чисел q и r, таких, что выполняются следующие условия: .

Легко доказывается, что для любых целых чисел а и деление с остатком возможно и числа q и r определяются однозначно. В нашем примере полная система наименьших неотрицательных вычетов есть множество <0, 1, 2, 3, 4, 5>; полная система наименьших положительных вычетов – множество <0, 1, 2, 3, 4, 5>; полная система наименьших по абсолютной величине вычетов – множество <-2,-1, 0, 1, 2, 3>; приведённая система вычетов – множество <1,5>, так как ; фактор-множество

Один из методов выполнения арифметических операций над данными целыми числами основан на простых положениях теории чисел. Идея этого метода состоит в том, что целые числа представляются в одной из непозиционных систем – в системе остаточных классов. А именно: вместо операций над целыми числами оперируют с остатками от деления этих чисел на заранее выбранные простые числа – модули .

Чаще всего числа выбирают из множества простых чисел.

Пусть …, .

Так как в кольце целых чисел имеет место теорема о делении с остатком, т. е. где , то кольцо Z, по определению, является евклидовым.

Таким образом, в качестве чисел можно выбрать остатки от деления числа А на р_i соответственно.

Система вычетов позволяет осуществлять арифметические операции над конечным набором чисел, не выходя за его пределы. Полная система вычетов по модулю n ― любой набор из n попарно несравнимых по модулю n целых чисел. Обычно в качестве полной системы вычетов по модулю n берутся наименьшие неотрицательные вычеты

Делении целых чисел a и m получается частное q и остаток r, такие что

a = m q + r, 0 r m-1. Остаток r называют ВЫЧЕТом по модулю m.

Например, для m = 3 и для m =5 получим:

a = m q + r, m = 3	a = m q + r, m = 5
0 = 3 + 0	0 = 5 + 0
1 = 3 + 1	1 = 5 + 1
2 = 3 + 2	2 = 5 + 2
3 = 3 + 0	3 = 5 + 3
4 = 3 + 1	4 = 5 + 4
5 = 3 + 2	5 = 5 + 0
6 = 3 + 0	6 = 5 + 1
7 = 3 + 1	7 = 5 + 2

Если остаток равен нулю (r=0), то говорят, что m делит a нацело ( или m кратно a), что обозначают m a , а числа q и m называют делителями a. Очевидно 1 a и a a. Если a не имеет других делителей, кроме 1 и а, то а – простое число, иначе а называют составным числом. Самый большой положительный делитель d двух чисел a и m называют наибольшим общим делителем (НОД) и обозначают d = (a,m). Если НОД (a,m)= 1, то a и m не имеют общих делителей, кроме 1, и называются взаимно простыми относительно друг друга.

Например, при m = 3:

Например, при m = 5:

Числа а тоже называют ВЫЧЕТамипо модулю m. НеотрицательныеВЫЧЕТы а = r (при q=0), принимающие значения из интервала [0, 1. m – 1], образуют полную систему наименьших вычетов по модулю m.

ВЫЧЕТы а, принимающие значения из интервала [-( ,…,( ], при нечетном m или из интервала [- при четном m образуют полную систему абсолютно наименьших ВЫЧЕТов по модулю m.

Например, при m = 5 классы наименьших вычетов образуют

Класс ВЫЧЕТов, элементы которого взаимно просты с модулем m

называют приведенным. Функция Эйлера определяет сколько ВЫЧЕТов из полной системы наименьших вычетов по модулю m взаимно просты с m. При простом m=p имеем = p-1.

Определение. Максимальный набор попарно несравнимых по модулю m чисел, взаимно простых с m, называется приведённой системой вычетов по модулю m. Всякая приведённая система вычетов по модулю m содержит элементов, где — функция Эйлера.

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

Попарную несравнимость можно проверить, заменив каждое число наименьшим неотрицательным вычетом; если повторений не будет, то это полная система вычетов.

Применим теорему о делении с остатком: a = m q + r.

13 = 6 2 + 1 13 1(mod 6); 8 = 6 1 + 2 8 2(mod 6);

-3 = 6 (-1) + 3 -3 3(mod 6); 10 = 6 1 + 4 10 4(mod 6);

35 = 6 5 + 5 35 5(mod 6); 60 = 6 10 + 0 60 0(mod 6).

Получили последовательность чисел: 1, 2, 3, 4, 5, 0, их ровно 6, повторений нет и они попарно несравнимы. То есть, они образуют полную систему вычетов по модулю m = 6.

Пример. Заменить наименьшим по абсолютной величине, а также наименьшим положительным вычетом 185 по модулю 16.

Решение. Применим теорему о делении с остатком:

185 = 16 11 + 9 185 9(mod 16).

Решение: Всякая приведённая система вычетов по модулю m содержит элементов, где — функция Эйлера. В нашем случае =4, ибо среди натуральных чисел только 1, 3, 7, 9 взаимно просты с 10 и не превосходят его. То есть, возможно, что эти четыре числа составляют искомую систему. Проверим эти числа на их попарную несравнимость:

Все числа попарно несравнимы, среди них нет повторений, их ровно 4 и они не превосходят модуль. Следовательно, они образуют приведенную систему вычетов.

Решение: В нашем случае =4, ибо среди натуральных чисел только 1, 3, 7, 9 взаимно просты с 10 и не превосходят его. То есть, возможно, что эти четыре числа составляют искомую систему. Проверим эти числа на их попарную несравнимость:

-349 = 12 (-30) + 11; -349 11(mod 12);

— 193 = 12 (-17) + 11; -193 11(mod 12);

231 = 12 19 + 3; 231 3(mod 12);

401 = 12 33 + 5; 401 5(mod 12).

КОНТРОЛЬНОЕ ЗАДАНИЕ

Задание 1. Заменить число а наименьшим по абсолютной величине, а также наименьшим положительным вычетом по модулю m.

Вариант 1. a = 185, m = 12; Вариант 2. a = 84, m = 9;

Вариант 3. a = 180, m = 10; Вариант 4. a = 82, m = 9;

Вариант 5. a = 85, m = 11; Вариант 6. a = 84, m = 8;

Вариант 7. a = 103, m = 87; Вариант 8. a = 84, m = 16;

Вариант 9. a = 15, m = 10; Вариант 10. a = 81, m = 9;

Вариант 11. a = 85, m = 15; Вариант 12. a = 74, m = 13;

Вариант 13. a = 185, m = 16; Вариант 14. a = 14, m = 9;

Вариант 15. a = 100, m = 11; Вариант 16. a = 484, m = 15;

Вариант 17. a = 153, m = 61; Вариант 18. a = 217, m = 19;

Вариант 19. a = 625, m = 25; Вариант 20. a = 624, m = 25;

Задание 3. Записать полную и приведенную систему наименьших

Источник