Что такое вычет по модулю кратко

Обновлено: 05.07.2024

и, притом, только с одним, потому что в противном случае между этими числами нашлось бы по крайней мере два числа, сравнимых по модулю 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, тогда

где 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. Понятие вычета.

Вычетом числа a по модулю m называется остаток от деления a на m

Из определения видно, что вычеты связаны с делением с остатком.

Разделить натуральное число a на натуральное число b с остатком означает yнайти неотрицательные числа два числа q и г, причем г (а ± с) º (b ± d)(mod p).

Слагаемые можно переносить из одной части сравнения в другую с противоположным знаком.

3. Сравнения можно перемножать:

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

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

6. Обе части сравнения можно возвести в степень (следствие свойства 3):

Понятие сравнения ввел К.Ф.Гаусс в работе Арифметические исследования (1802). Алгебра вычетов возникает в тех случаях, когда рассматриваются некоторые циклически повторяющиеся события, например время в течение дня, повторяющееся каждые 24 часа, углы по окружности, повторяющиеся через период 2к, и т.д.

Алгебра вычетов один из тех разделов математики, которые рождались как некоторые формальные рассуждения и только спустя годы нашли свое практическое применение.

Задание 9-2. Для степени y=2 n (n–натуральное число) установить классы сравнимости. Установить зависимость последней цифры этой степени от ее показателя.

Решение и комментарии.

Как известно, натуральные степени числа 2 оканчиваются цифрами . См. таблицу нескольких степеней числа 2.

Определим функцию, которая ставит в соответствие каждому натуральному числу п последнюю цифру числа 2 я :

Эта функция f(n) периодична с периодом 4. Это значит, что для целого числа k: f(n)=f(n+4)= f(n+4k),.

Причем справедливы так же равенства: f(n)=f(n-4)= f(n-4k)

Но это задача на делении с остатком числа n на 4:

n=4k+m, k- частное, т остаток.

Очевидно, последняя цифра числа 2 зависит от остатка, полученного при делении показателя n степени 2 n на 4.

Отразим этот факт в записи функции: f(n)= f(n mod 4)

Из этой формулы можно установить, если f(n mod 4)=0, то

При делении чисел на 4 nÎN, останки могут быть: 0,1,2,3. Таким образом, в частности, множество всех возможных показателей степени 2 n для любого n состоит из четырех подмножеств: 4k, 4k+ 1, 4k+ 2, 4k+3.

Задание 9-3. Установить последнюю цифру степени y=2 2007

Решение. Имеем 2007=501·4+3, значит f (2007)=f (3)=2 3 =8. Ответ 8.

Требования к знаниям умениям и навыкам

Студенты должны знать определения вычета. Иметь представление о выполнении операций над вычетами. Иметь представление о числовом и цифровом кодировании.

$a = q \times n + r$

Уравнение деления ( ), рассмотренное в предыдущей секции, имеет два входа ( a и n ) и два выхода ( q и r ). В модульной арифметике мы интересуемся только одним из выходов — остатком r . Мы не заботимся о частном q . Другими словами, когда мы делим a на n , мы интересуемся только тем, что значение остатка равно r . Это подразумевает, что мы можем представить изображение вышеупомянутого уравнения как бинарный оператор с двумя входами a и n и одним выходом r .

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

Вышеупомянутый бинарный оператор назван оператором по модулю и обозначается как mod . Второй вход ( n ) назван модулем. Вывод r назван вычетом. Рисунок 2.9 показывает отношение деления по сравнению с оператором по модулю.

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

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

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

Мы ищем вычет r . Мы можем разделить a на n и найти q и r . Далее можно игнорировать q и сохранить r .

а. Разделим 27 на 5 - результат: r = 2 . Это означает, что 27 mod 5 = 2 .

б. Разделим 36 на 12 — результат: r = 0 . Это означает, что 36 mod 12 = 0 .

в. Разделим (–18) на 14 — результат: r = –4 . Однако мы должны прибавить модуль (14) , чтобы сделать остаток неотрицательным. Мы имеем r = –4 + 14 = 10 . Это означает, что –18 mod 14 = 10 .

г. Разделим (–7) на 10 — результат: r = –7 . После добавления модуля –7 мы имеем r = 3 . Это означает, что –7 mod 10 = 3 .

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

Результат операции по модулю n — всегда целое число между 0 и n - 1 . Другими словами, результат a mod n — всегда неотрицательное целое число, меньшее, чем n . Мы можем сказать, что операция по модулю создает набор, который в модульной арифметике можно понимать как систему наименьших вычетов по модулю n, или Z_n . Однако мы должны помнить, что хотя существует только одно множество целых чисел ( Z ), мы имеем бесконечное число множеств вычетов ( Z_n ), но лишь одно для каждого значения n . Рисунок 2.10 показывает множество Z_n и три множества Z₂ , Z₆ и Z₁₁ .

Сравнения

$\equiv$

В криптографии мы часто используем понятие сравнения вместо равенства. Отображение Z в Z_n не отображаются "один в один". Бесконечные элементы множества Z могут быть отображены одним элементом Z_n . Например, результат 2 mod 10 = 2 , 12 mod 10 = 2 , 22 mod 10 = 2 , и так далее. В модульной арифметике целые числа, подобные 2 , 12 , и 22 , называются сравнимыми по модулю 10 (mod 10) . Для того чтобы указать, что два целых числа сравнимы, мы используем оператор сравнения ( ). Мы добавляем mod n к правой стороне сравнения, чтобы определить значение модуля и сделать равенство правильным. Например, мы пишем:

$2 \equiv 12 (mod \ 10) \ \ 13 \equiv 23 (mod \ 10) \ \ 34 \equiv 24 (mod \ 10) \ \ –8 \equiv 12 (mod \ 10) \\ 3 \equiv 8 (mod \ 5) \ \ 8 \equiv 13 (mod \ 5) \ \ 23 \equiv 33 (mod \ 5) \ \ -8 \equiv 2 (mod \ 5)$

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

a. Оператор сравнения напоминает оператор равенства, но между ними есть различия. Первое: оператор равенства отображает элемент Z самого на себя; оператор сравнения отображает элемент Z на элемент Z_n . Второе: оператор равенства показывает, что наборы слева и справа соответствуют друг другу "один в один", оператор сравнения — "многие — одному".

$2 \equiv 12(\bmod 10)$

б. Обозначение ( mod n ), которое мы вставляем с правой стороны оператора сравнения, обозначает признак множества ( Z_n ). Мы должны добавить это обозначение, чтобы показать, какой модуль используется в отображении. Символ, используемый здесь, не имеет того же самого значения, как бинарный оператор в уравнении деления. Другими словами, символ mod в выражении 12 mod 10 — оператор; а сочетание ( mod 10 ) в сравнении означает, что набор — Z₁₀ .

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

Система вычетов [a] , или [a]_n , — множество целых чисел, сравнимых по модулю n . Другими словами, это набор всех целых чисел, таких, что x = a (mod n) . Например, если n = 5 , мы имеем множество из пяти элементов [0] , [1] , [2] , [3] и [4] , таких как это показано ниже:

Целые числа в наборе [0] все дают остаток 0 при делении на 5 (сравнимы по модулю 5 ). Целые числа в наборе [1] все дают остаток 1 при делении на 5 (сравнимы по модулю 5 ), и так далее. В каждом наборе есть один элемент, называемый наименьшим (неотрицательным) вычетом. В наборе [0] это элемент 0 ; в наборе [1] — 1 , и так далее. Набор, который показывает все наименьшие вычеты: Z₅ = . Другими словами, набор Z_n — набор всех наименьших вычетов по модулю n.

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

Понятие "сравнение" может быть лучше раскрыто при использовании круга в качестве модели. Так же, как мы применяем линию, чтобы показать распределение целых чисел в Z , мы можем использовать круг, чтобы показать распределение целых чисел в Z_n .

Рисунок 2.12 позволяет сравнить два этих подхода. Целые числа от 0 до n–1 расположены равномерно вокруг круга. Все целые числа, сравнимые по модулю n , занимают одни и те же точки в круге. Положительные и отрицательные целые числа от Z отображаются в круге одним и тем же способом, соблюдая симметрию между ними.

Мы пользуемся сравнением по модулю в нашей ежедневной жизни; например, мы применяем часы, чтобы измерить время. Наша система часов использует арифметику по модулю 12 . Однако вместо 0 мы берем отсечку 12 , так что наша система часов начинается с 0 (или 12 ) и идет до 11 . Поскольку наши сутки длятся 24 часа, мы считаем по кругу два раза и обозначаем первое вращение как утро до полудня, а второе — как вечер после полудня.

Операции в Zn

Три бинарных операции ( сложение, вычитание и умножение ), которые мы обсуждали для Z , могут также быть определены для набора Z_n . Результат, возможно, должен быть отображен в Z_n с использованием операции по модулю, как это показано на рис. 2.13.

$( + ,-, \times )$

Фактически применяются два набора операторов: первый набор — один из бинарных операторов ; второй — операторы по модулю. Мы должны использовать круглые скобки, чтобы подчеркнуть порядок работ. Как показано на рис. 2.13, входы ( a и b ) могут быть членами Z или Z_n .

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

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

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

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

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

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

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

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

c. Умножение 123 на -10 в Z₁₉

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

Свойства

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

Второе свойство: (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 показывает процесс до и после применения указанных выше свойств. Хотя по рисунку видно, что процесс с применением этих свойств более длинен, мы должны помнить, что в криптографии мы имеем дело с очень большими целыми числами. Например, если мы умножаем очень большое целое число на другое очень большое целое число, которое настолько большое, что не может быть записано в компьютере, то применение вышеупомянутых свойств позволяет уменьшить первые два операнда прежде, чем начать умножение. Другими словами, перечисленные свойства позволяют нам работать с меньшими числами. Этот факт станет понятнее при обсуждении экспоненциальных операций в последующих лекциях.

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

В арифметике мы часто должны находить остаток от степеней числа 10 при делении на целое число. Например, мы должны найти 10 mod 3 , 10 2 mod 3 , 10 3 mod 3 , и так далее. Мы также должны найти 10 mod 7 , 10 2 mod 7 , 10 3 mod 7 , и так далее. Третье свойство модульных операторов, упомянутое выше, делает жизнь намного проще.

Определение. Числа образуют полную систему вычетов по модулю , если любое целое число сравнимо по модулю с одним и только одним из этих чисел.

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

Теорема. Пусть — полная система вычетов по модулю . Пусть — целое число, взаимно простое с . Тогда — тоже полная система вычетов по модулю .

Доказательство. Нужно доказать, что эти числа попарно не сравнимы по модулю . Предположим противное. Пусть

$xa_i\equiv xa_k\pmod<m> \qquad(a_i\ne a_k).$

$a_i\equiv a_k\pmod<m> Так как НОД , то$
, что противоречит условию.

Теорема. Пусть — полная система вычетов по модулю . Пусть — целое число. Тогда — тоже полная система вычетов по модулю .

$a\equiv b\pmod<m> Лемма. Если$
, то НОД НОД .

Доказательство.

$a\equiv b\pmod<m> \Longrightarrow a-b\vdots m\Longrightarrow a-b=km,\ k$
– целое число.

Отсюда . Любой общий делитель и является делителем . Отсюда НОД НОД .

Определение. Числа образуют приведенную систему вычетов по модулю , если они взаимно просты с и любое целое число, взаимно простое с , сравнимо с одним и только одним из этих чисел по модулю .

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

Лемма. Все приведенные системы вычетов по модулю состоят из одного и того же количества чисел, которое обозначается — функция Эйлера.

Доказательство. Действительно, пусть есть две приведенные системы вычетов по модулю , состоящие из разного количества чисел:

Тогда так как числа образуют приведенную систему вычетов по модулю , то каждое из чисел сравнимо с одним и только одним из этих чисел. Поскольку , то, по принципу Дирихле, по крайней мере два числа из будут сравнимы с каким-то числом , а значит, будут сравнимы между собой по модулю . А это противоречит тому, что — приведенная система вычетов по модулю . Значит, .

Докажем теперь, что . В самом деле, числа, меньшие и взаимно простые с , образуют приведенную систему вычетов по модулю . Это следует из леммы.

Определение. Функция Эйлера (или тотиент) обозначает количество чисел, меньших и взаимно простых с .

Теорема. Если — приведенная система вычетов по модулю и — число, взаимно простое с , то — тоже приведенная система вычетов по модулю .

Если — простое, то .

$\varphi(p^k)=p^k-p^<k-1> Лемма. Если — простое, то$
.

Лемма. Пусть НОД . Тогда . Функция Эйлера мультипликативна.

Доказательство. Запишем все числа от до следующим образом:

$\begin 1&2&3&\ldots&a\\ a+1&a+2&a+3&\ldots&2a\\ 2a+1&2a+2&2a+3&\ldots&3a\\ \ldots&&&&\\ (b-1)a+1&(b-1)a+2&(b-1)a+3&\ldots&ab \end$

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

Числа в каждом столбце образуют полную систему вычетов по модулю . Действительно, -й столбец получается, если взять числа , образующие полную систему вычетов по модулю , умножить их на число , взаимно простое с , и прибавить к каждому из них .

Таким образом, в каждом столбце ровно чисел, взаимно простых с .

Так как число будет взаимно простым с тогда и только тогда, когда оно взаимно просто с и взаимно просто с , то количество чисел, взаимно простых с , равно .

Теорема. Пусть

$a=p_1^<k_1> p_2^\dots p_n^$

— каноническое разложение числа . Тогда

$\begin \displaystyle \varphi(a)=a\left(1-<1\over p_1>\right)\left(1-<1\over p_2>\right)\ldots \left(1-<1\over p_n>\right)=\\[3mm] \displaystyle =(p^-p^)(p_2^-p_2^)\dots(p_n^-p_n^). \end$

Доказательство. По лемме о мультипликативности функции Эйлера

$\varphi(p_1^ p_2^\ldots p_n^)=\varphi(p_1^)\varphi(p_2^)\ldots \varphi(p_n^).$

$\varphi(p_j^<k_j> А далее каждое )$
вычисляем по лемме о вычислении функции Эйлера для простых чисел.

Пример.

$\varphi(4)=2,\varphi(10)=4,\varphi(100)=40,\varphi(1000)=400.$

Теорема (Эйлера). Если x и m — взаимно простые числа, то

$x^<\varphi(m)> \equiv1\pmod.$

Пусть — какая-нибудь приведенная система вычетов по модулю . . Тогда — тоже приведенная система вычетов по модулю . Следовательно, каждое из чисел первой последовательности сравнимо с одним из чисел второй последовательности по модулю , а каждое из чисел второй последовательности сравнимо с одним из чисел первой последовательности. Тогда

$xa_1\cdot xa_2\cdot\ldots\cdot xa_k\equiv a_1a_2\cdot\ldots\cdot a_k\pmod<m> .$

Так как каждое из чисел взаимно просто с , то на них сравнение можно сократить:

$\begin x^k\equiv1\pmod\\ x^\equiv1\pmod. \end$

Следствие. Пусть – целые числа, – натуральные. Если " width="117" height="18" />
, " width="146" height="18" />
, НОД , то " width="134" height="18" />
.

Доказательство. Пусть . Так как " width="146" height="18" />
, то — натуральное число. Тогда

$a^n=a^<p+k\varphi(m)> =a^p\cdot\left(a^\right)^k\equiv a^p\pmod.$

$a^p\equiv b^p\pmod<m> $
.

$a^n\equiv b^p\pmod<m> Значит,$
.

Именем Леонарда Эйлера (1707–1783) в современной математике названы: критерий, метод, многочлены, подстановки, постоянная, преобразование, произведение, ряд, теоремы, тождества, уравнения, формулы, функции, характеристика, интегралы, углы, числа и т.д. Гений XVIII в. — Леонард Эйлер — обрел в России вторую родину и проработал в Петербургской академии наук более 30 лет. Французский математик П.С. Лаплас советовал: “Читайте, читайте Эйлера — он учитель нас всех”.

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

В 1741 году Эйлер, по приглашению Фридриха II, приезжает из Петербурга в Берлинскую академию наук. Ученого приняли с большими почестями. На одном из королевских приемов во дворце мать короля обратила внимание Эйлера, что он отвечает ей односложно “да” и “нет”. “Почему же Вы не хотите со мной говорить?” — спросила она Эйлера. “Сударыня, — ответил ученый, — я приехал из страны, где тех, кто говорит, вешают”. Ответ Эйлера показывает, в каких трудных условиях приходилось работать в Петербургской академии того времени.

Выдающийся французский математик Пьер Ферма (1601–1665) был по профессии юрист. В теории чисел с его именем связаны знаменитые теоремы: великая теорема Ферма и малая теорема Ферма. В геометрии Ферма явился непосредственным предшественником Декарта. Важную роль сыграл Ферма в зарождении теории вероятности. В трудах Ферма получили систематическое развитие операции дифференцирования и интегрирования. С именем Ферма связано установление вариационного принципа геометрической оптики.

Задачи.

$a_1+a_2+\ldots+a_s\equiv0\pmod<m> 1. Докажите, что если — приведенная система вычетов по модулю , то$
.

$(p-1)!\equiv-1\pmod2. Докажите,что если — простое число, то$
(теорема Вильсона).

$p\equiv1\pmod<4> 3. Докажите, что если — простое число и$
, то найдется такое целое число , что делится на .

$p\equiv1\pmod<4> 4. Докажите, что если — целое число и — нечетный простой делитель числа , то$
.

$a_1a_2\ldots a_s\equiv\pm1\pmod<m> 5. Докажите, что если > — приведенная система вычетов по модулю , то$
.

6. Докажите, что если — приведенная система вычетов по модулю и существует " width="133" height="18" />
, такое что " width="127" height="19" />
, то " width="186" height="18" />
.

на .

8. Докажите, что если — целые числа и делится на , то делится на .

$(a+b)^p\equiv a^p+b^p\pmod9. Докажите, что если и — целые числа и — простое число, то$
.

$p^<q-1> 10. Пусть и — различные простые числа. Докажите, что +q^\equiv1\pmod$
.

11. Докажите, что при всех число не делится на .

Читайте также: