полная система вычетов по модулю m это

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

Совокупность чисел, сравнимых с a по модулю m называется классом чисел по модулю m (или классом эквивалентности). Все числа одного класса имеют вид mt + r при фиксированном r.

При заданном m, r может принимать значения от 0 до m—1, т.е. всего существует m классов чисел по модулю m, и любое целое число попадет в один из классов по модулю m. Таким образом,

Z = [0]_m [1]_m … [m—1]_m, где [r]_m=<x Z: x≡r(mod m)>

Любое число класса [r]_m называется вычетом по модулю m по отношению ко всем числам того же класса. Число, равное остатку r, называется наименьшим неотрицательным вычетом.

Вычет, наименьший по абсолютной величине, называется абсолютно наименьшим вычетом.

Возьмем модуль m=5. И пусть a=8. Разделим a на m с остатком:

Остаток r=3. Значит 8 [3]₅, и наименьший неотрицательный вычет числа 8 по модулю 5 есть 3.

Абсолютно наименьший вычет можно отыскать, вычислив r—m=3—5=—2, и сравнив абсолютные величины |—2| и |3|. |—2|

Дата добавления: 2015-11-28 ; просмотров: 7342 ; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ

Источник

Сравнения, система вычетов, решение линейных систем по модулю

Содержание

Сравнения по модулю [ править ]

Будем рассматривать целые числа в связи с остатками от деления их на данное целое число m, которое назовем модулем. Каждому целому числу отвечает определенный остаток от деления его на m. Если двум целым a и b отвечает один и тот же остаток r, то они называются сравнимыми по модулю m.

Сравнимость для a и b записывается так :
[math]a \equiv b(mod \text < >m)[/math]

Сравнимость чисел a и b по модулю m равносильна:

Арифметика сравнений [ править ]

Свойства сравнений [ править ]

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

Числа равноостаточные(сравнимые по модулю m) образуют класс чисел по модулю m. Из такого определения следует, что всем числам класса отвечает один остаток r, и мы получим все числа класса, если в форме [math]mt + r [/math] заставим t пробегать все целые числа. Таким образом для каждого значения остатка имеется свой класс чисел.

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

Согласно 10 свойству сравнений, числа одного класса по модулю m имеют одинаковый НОД. Особенно важны классы, содержащие числа, взаимно простые с модулем. Взяв вычет от каждого такого класса, получим приведенную систему вычетов по модулю m.

Решение линейных систем по модулю [ править ]

Примеры решения [ править ]

Источник

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

Как известно из статьи «Сравнение чисел по модулю»), всякое число 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. Если двум целым a и b отвечает один и тот же остаток r, то они называются сравнимыми по модулю m.

Сравнимость для a и b записывается так :
[math]a \equiv b(mod \text < >m)[/math]

Сравнимость чисел a и b по модулю m равносильна:

Арифметика сравнений [ править ]

Свойства сравнений [ править ]

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

Числа равноостаточные(сравнимые по модулю m) образуют класс чисел по модулю m. Из такого определения следует, что всем числам класса отвечает один остаток r, и мы получим все числа класса, если в форме [math]mt + r [/math] заставим t пробегать все целые числа. Таким образом для каждого значения остатка имеется свой класс чисел.

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

Согласно 10 свойству сравнений, числа одного класса по модулю m имеют одинаковый НОД. Особенно важны классы, содержащие числа, взаимно простые с модулем. Взяв вычет от каждого такого класса, получим приведенную систему вычетов по модулю m.

Решение линейных систем по модулю [ править ]

Примеры решения [ править ]

Источник

Модульная арифметика

2.2. Модульная арифметика

Операции по модулю

Как показано на рис. 2.9, оператор по модулю ( mod ) выбирает целое число ( a ) из множества Z и положительный модуль ( n ). Оператор определяет неотрицательный остаток ( r ).

Мы можем сказать, что

Найти результат следующих операций:

Система вычетов: Zn

Сравнения

Рисунок 2.11 показывает принцип сравнения. Мы должны объяснить несколько положений.

Система вычетов

Круговая система обозначений

Операции в Zn

Выполните следующие операторы (поступающие от Z_n ):

а. Сложение 7 и 14 в Z₁₅

б. Вычитание 11 из 7 в Z₁₃

в. Умножение 11 на 7 в Z₂₀

Ниже показаны два шага для каждой операции:

Выполните следующие операции (поступающие от Z_n ):

a. Сложение 17 и 27 в Z₁₄

b. Вычитание 43 из 12 в Z₁₃

Ниже показаны два шага для каждой операции:

Свойства

Первое свойство: (a + b) mod n = [(a mod n) + (b mod n)] mod n

Третье свойство: (a x b) mod n = [(a mod n) x (b mod n)] mod n

Рисунок 2.14 показывает процесс до и после применения указанных выше свойств. Хотя по рисунку видно, что процесс с применением этих свойств более длинен, мы должны помнить, что в криптографии мы имеем дело с очень большими целыми числами. Например, если мы умножаем очень большое целое число на другое очень большое целое число, которое настолько большое, что не может быть записано в компьютере, то применение вышеупомянутых свойств позволяет уменьшить первые два операнда прежде, чем начать умножение. Другими словами, перечисленные свойства позволяют нам работать с меньшими числами. Этот факт станет понятнее при обсуждении экспоненциальных операций в последующих лекциях.

Следующие примеры показывают приложение вышеупомянутых свойств.

Источник