Примеры использования сравнения по модулю. Сравнение чисел по модулю. Вычисление обратного элемента по заданному модулю

Сравнение с одним неизвестным x имеет вид

Где . Еслиa n не делится на m , то и называется степенью сравнения.

Решением сравнения называется всякое целое число x 0 , для которого

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

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

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

Сравнение первой степени с одним неизвестным х имеет вид

(2.2)

Теорема2.4. Для того чтобы сравнение имело хотя бы одно решение, необходимо и достаточно, чтобы число b делилось на НОД(a , m ).

Доказательство. Сначала докажем необходимость. Пусть d = НОД(a , m ) и х 0 - решение сравнения. Тогда, то есть разностьах 0 − b делится на т. Значит, существует такое целое число q , что ах 0 − b = qm . Отсюда b = ах 0 − qm . А поскольку d , как общий делитель, делит числа а и т, то уменьшаемое и вычитаемое делятся на d , а значит и b делится на d .

Теперь докажем достаточность. Пусть d - наибольший общий делитель чисел а и т, и b делится на d . Тогда по определению делимости существуют такие целые числа a 1 , b 1 ,т 1 , что.

Расширенным алгоритмом Евклида найдем линейное представление числа 1 = НОД(a 1 , m 1 ):

для некоторых x 0 , y 0 . Домножим обе части последнего равенства на b 1 d :

или, что то же самое,

,

то есть , и- решение сравнения. □

Пример2.10. Сравнение 9х = 6 (mod 12) имеет решение, так как НОД(9, 12) = 3 и 6 делится на 3. □

Пример2.11. Сравнение 6х = 9 (mod 12) не имеет решений, так как НОД(6, 12) = 6, а 9 не делится на 6. □

Теорема 2.5. Пусть сравнение (2.2) разрешимо и d = НОД(a , m ). Тогда множество решений сравнения (2.2) состоит из d классов вычетов по модулю т, а именно, если х 0 - одно из решений, то все другие решения - это

Доказательство. Пусть х 0 - решение сравнения (2.2), то есть и, . Значит, существует такое q , что ах 0 − b = qm . Подставляя теперь в последнее равенство вместо х 0 произвольное решение вида, где, получаем выражение

, делящееся на m . □

Пример 2.12. Сравнение 9х =6 (mod 12) имеет ровно три решения, так как НОД(9, 12)=3. Эти решения: х 0 = 2, х 0 + 4 = 6, х 0 + 2∙4=10.□

Пример2.13. Сравнение 11х =2 (mod 15) имеет единственное решение х 0 = 7,таккакНОД(11,15)=1.□

Покажем, как решать сравнение первой степени. Не умаляя общности, будем считать, что НОД(a , т) = 1. Тогда решение сравнения (2.2) можно искать, например, по алгоритму Евклида. Действительно, используя расширенный алгоритм Евклида, представим число 1 в виде линейной комбинации чисел a и т :

Умножим обе части этого равенства на b , получим: b = abq + mrb , откуда abq - b = - mrb , то есть a ∙ (bq ) = b (mod m ) и bq - решение срав­нения (2.2).

Еще один путь решения - использовать теорему Эйлера. Опять считаем, что НОД(а, т) = 1. Применяем теорему Эйлера: . Умножим обе части сравнения наb : . Переписывая последнее выражение в виде , получаем, что- решение сравнения (2.2).

Пусть теперь НОД(a , m ) = d >1. Тогда a = a t d , m = m t d , где НОД(а 1 , m 1) = 1. Кроме того, необходимо b = b 1 d , для того чтобы сравнение было разрешимо. Если х 0 - решение сравнения а 1 x = b 1 (mod m 1), причем единственное, поскольку НОД(а 1 , m 1) = 1, то х 0 будет решением и сравнения а 1 xd = db 1 (mod m 1), то есть исходного сравнения (2.2). Остальные d - 1 решений находим по теореме 2.5.

Сравнение первой степени с одним неизвестным имеет вид:

f (x ) 0 (mod m ); f (х ) = ах + а n . (1)

Решить сравнение – значит найти все значения х, ему удовлетворяющие. Два сравнения, которым удовлетворяют одни и те же значения х, называются равносильными .

Если сравнению (1) удовлетворяет какое-либо x = x 1, то (согласно 49) тому же сравнению будут удовлетворять и все числа, сравнимые с x 1 , по модулю m : x x 1 (mod m ). Весь этот класс чисел считается за одно решение . При таком соглашении можно сделать следующий вывод.

66.Сравнение (1) будет иметь столько решений, сколько вычетов полной системы ему удовлетворяет .

Пример. Сравнению

6x – 4 0 (mod 8)

среди чисел 0, 1,2, 3, 4, 5, 6, 7 полной системы вычетов по модулю 8 удовлетворяют два числа: х = 2 и х = 6. Поэтому указанное сравнение имеет два решения:

x 2 (mod 8), х 6 (mod 8).

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

ax b (mod m ). (2)

Рассмотрим сравнение, удовлетворяющее условию (а , m ) = 1.

Согласно 66 наше сравнение имеет столько решений, сколько вычетов полной системы ему удовлетворяет. Но когда x пробегает полную систему вычетов по модулю т, то ах пробегает полную систему вычетов (из 60). Следовательно, при одном и только одном значении х, взятом из полной системы, ах будет сравнимо с b. Итак,

67. При (а, m) = 1 сравнение ax b (mod m ) имеет одно решение.

Пусть теперь (a , m ) = d > 1. Тогда, чтобы сравнение (2) имело решения, необходимо (из 55), чтобы b делилось на d, иначе сравнение (2) невозможно ни при каком целом х. Предполагая, поэтому b кратным d, положим a = a 1 d , b = b 1 d , m = m 1 d. Тогда сравнение (2) будет равносильно такому (по сокращении на d ): a 1 x b 1 (mod m ), в котором уже (а 1 , m 1) = 1, и потому оно будет иметь одно решение по модулю m 1 . Пусть х 1 – наименьший неотрицательный вычет этого решения по модулю m 1, тогда все числа х, образующие это решение, найдутся в виде

x x 1 (mod m 1). (3)

По модулю же mчисла (3) образуют не одно решение, а больше, именно столько решений, сколько чисел (3) найдется в ряде 0, 1, 2, ..., m – 1 наименьших неотрицательных вычетов по модулю m. Но сюда попадут следующие числа (3):

x 1 , x 1 + m 1 , x 1 + 2m 1 , ..., x 1 + (d – 1) m 1 ,

т.е. всего d чисел (3); следовательно, сравнение (2) имеет d решений.

Получаем теорему:

68. Пусть (a, m) = d. Сравнение ax b (mod m) невозможно, если b не делится на d. При b, кратном d, сравнение имеет d решений..

69.Способ решения сравнения первой степени, основанный на теории непрерывных дробей:

Разлагая в непрерывную дробь отношение m:а ,

и рассматривая две последние подходящие дроби:

согласно свойствам непрерывных дробей (согласно 30 ) имеем

Итак, сравнение имеет решение

для разыскания, которого достаточно вычислить P n – 1 согласно способу, указанному в 30.

Пример. Решим сравнение

111x = 75 (mod 321). (4)

Здесь (111, 321) = 3, причем 75 кратно 3. Поэтому сравнение имеет три решения.

Деля обе части сравнения и модуль на 3, получим сравнение

37x = 25 (mod 107), (5)

которое нам следует сначала решить. Имеем

q
P 3

Значит, в данном случае n = 4, P n – 1 = 26, b = 25, и мы имеем решение сравнения (5) в виде

x –26 ∙ 25 99 (mod 107).

Отсюда решения сравнения (4) представляются так:

х 99; 99 + 107; 99 + 2 ∙ 107 (mod 321),

х º99; 206; 313 (mod 321).

Вычисление обратного элемента по заданному модулю

70.Если целые числа a и n взаимно просты, то существует число a′ , удовлетворяющее сравнению a ∙ a′ ≡ 1(mod n ). Число a′ называется мультипликативным обратным к a по модулю n и для него используется обозначение a - 1 (mod n ).

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

Чтобы найти решение сравнения

a ∙x ≡ 1(mod m ),

где (a,m )= 1,

можно воспользоваться алгоритмом Евклида (69) или теоремой Ферма-Эйлера, которая утверждает, что если (a,m ) = 1, то

a φ( m ) ≡ 1(mod m ).

x ≡ a φ( m )–1 (mod m ).

Группы и их свойства

Группы – один из таксономических классов, используемых при классификации математических структур с общими характерными свойствами. Группы имеют две составляющие: множество (G ) и операции (), определенные на этом множестве.

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

Для двух множеств A, B записи B A , B A , B ∩ A , B A , B \ A , A × B означают соответственно, что B является подмножеством множества A (т.е. любой элемент из B содержится также и в A , например, множество натуральных чисел содержится в множестве действительных чисел; кроме того, всегда A A ), B является собственным подмножеством множества A (т.е. B A и B ≠ A ), пересечение множеств B и A (т.е. все такие элементы, которые лежат одновременно и в A , и в B , например пересечение целых чисел и положительных действительных чисел есть множество натуральных чисел), объединение множеств B и A (т.е. множество, состоящее из элементов, которые лежат либо в A , либо в B ), разность множеств B и A (т.е. множество элементов, которые лежат в B , но не лежат в A ), декартово произведение множеств A и B (т.е. множество пар вида (a , b ), где a A , b B ). Через |A | всегда обозначается мощность множества A , т.е. количество элементов в множестве A .

Операция – это правило, согласно которому любым двум элементам множества G (a и b ) ставится в соответствие третий элемент из G: а b.

Множество элементов G с операцией называется группой , если удовлетворяются следующие условия.

Рассмотрим сравнение вида x 2 ≡a (mod p α), где p – простое нечетное число. Как было показано в п.4 §4, решение этого сравнения можно отыскать, решив сравнение x 2 ≡a (mod p ). Причем сравнение x 2 ≡a (mod p α) будет иметь два решения, если a является квадратичным вычетом по модулю p .

Пример:

Решить квадратичное сравнение x 2 ≡86(mod 125).

125 = 5 3 , 5 – простое число. Проверим, является ли 86 квадратом по модулю 5.

Исходное сравнение имеет 2 решения.

Найдем решение сравнения x 2 ≡86(mod 5).

x 2 ≡1(mod 5).

Это сравнение можно было бы решить способом, указанным в предыдущем пункте, но мы воспользуемся тем, что квадратный корень из 1 по любому модулю есть ±1, а сравнение имеет ровно два решения. Таким образом, решение сравнения по модулю 5 есть

x ≡±1(mod 5) или, иначе, x =±(1+5t 1).

Подставим получившееся решение в сравнение по модулю 5 2 =25:

x 2 ≡86(mod 25)

x 2 ≡11(mod 25)

(1+5t 1) 2 ≡11(mod 25)

1+10 t 1 +25 t 1 2 ≡11(mod 25)

10 t 1 ≡10(mod 25)

2 t 1 ≡2(mod 5)

t 1 ≡1(mod 5), или, что то же самое, t 1 =1+5t 2 .

Тогда решение сравнения по модулю 25 есть x =±(1+5(1+5t 2))=±(6+25t 2). Подставим получившееся решение в сравнение по модулю 5 3 =125:

x 2 ≡86(mod 125)

(6+25t 2) 2 ≡86(mod 125)

36+12·25t 2 +625t 2 2 ≡86(mod 125)

12·25t 2 ≡50(mod 125)

12t 2 ≡2(mod 5)

2t 2 ≡2(mod 5)

t 2 ≡1(mod 5), или t 2 =1+5t 3 .

Тогда решение сравнения по модулю 125 есть x =±(6+25(1+5t 3))=±(31+125t 3).

Ответ: x ≡±31(mod 125).

Рассмотрим теперь сравнение вида x 2 ≡a (mod 2 α). Такое сравнение не всегда имеет два решения. Для такого модуля возможны случаи:

1) α=1. Тогда сравнение имеет решение только тогда, когда a ≡1(mod 2), и решением будет x ≡1(mod 2) (одно решение).

2) α=2. Сравнение имеет решения только тогда, когда a ≡1(mod 4), и решением будет x ≡±1(mod 4) (два решения).

3) α≥3. Сравнение имеет решения только тогда, когда a ≡1(mod 8), и таких решений будет четыре. Сравнение x 2 ≡a (mod 2 α) при α≥3 решается так же, как сравнения вида x 2 ≡a (mod p α), только в качестве начального решения выступают решения по модулю 8: x ≡±1(mod 8) и x ≡±3(mod 8). Их следует подставить в сравнение по модулю 16, затем по модулю 32 и т. д. вплоть до модуля 2 α .

Пример:

Решить сравнение x 2 ≡33(mod 64)

64=2 6 . Проверим, имеет ли исходное сравнение решения. 33≡1(mod 8), значит сравнение имеет 4 решения.

По модулю 8 эти решения будут: x ≡±1(mod 8) и x ≡±3(mod 8), что можно представить как x =±(1+4t 1). Подставим это выражение в сравнение по модулю 16

x 2 ≡33(mod 16)

(1+4t 1) 2 ≡1(mod 16)

1+8t 1 +16t 1 2 ≡1(mod 16)

8t 1 ≡0 (mod 16)

t 1 ≡0 (mod 2)

Тогда решение примет вид x =±(1+4t 1)=±(1+4(0+2t 2))=±(1+8t 2). Подставим получившееся решение в сравнение по модулю 32:

x 2 ≡33(mod 32)

(1+8t 2) 2 ≡1(mod 32)

1+16t 2 +64t 2 2 ≡1(mod 32)

16t 2 ≡0 (mod 32)

t 2 ≡0 (mod 2)

Тогда решение примет вид x =±(1+8t 2) =±(1+8(0+2t 3)) =±(1+16t 3). Подставим получившееся решение в сравнение по модулю 64:

x 2 ≡33(mod 64)

(1+16t 3) 2 ≡33(mod 64)

1+32t 3 +256t 3 2 ≡33(mod 64)

32t 3 ≡32 (mod 64)

t 3 ≡1 (mod 2)

Тогда решение примет вид x =±(1+16t 3) =±(1+16(1+2t 4)) =±(17+32t 4). Итак, по модулю 64 исходное сравнение имеет четыре решения: x ≡±17(mod 64)и x ≡±49(mod 64).

Теперь рассмотрим сравнение общего вида: x 2 ≡a (mod m ), (a ,m )=1, - каноническое разложение модуля m . Согласно Теореме из п.4 §4, данному сравнению равносильна система

Если каждое сравнение этой системы разрешимо, то разрешима и вся система. Найдя решение каждого сравнения этой системы, мы получим систему сравнений первой степени, решив которую по китайской теореме об остатках, получим решение исходного сравнения. При этом количество различных решений исходного сравнения (если оно разрешимо) есть 2 k , если α=1, 2 k +1 , если α=2, 2 k +2 , если α≥3.

Пример:

Решить сравнение x 2 ≡4(mod 21).

На n они дают одинаковые остатки.

Эквивалентные формулировки: a и b сравнимы по модулю n , если их разность a - b делится на n , или если a может быть представлено в виде a = b + k n , где k - некоторое целое число. Например: 32 и −10 сравнимы по модулю 7, так как

Утверждение « a и b сравнимы по модулю n » записывается в виде:

Свойства равенства по модулю

Отношение сравнения по модулю обладает свойствами

Любые два целых числа a и b сравнимы по модулю 1.

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

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

Если числа a и b сравнимы по модулю n , то их степени a k и b k тоже сравнимы по модулю n при любом натуральном k .

Если числа a и b сравнимы по модулю n , и n делится на m , то a и b сравнимы по модулю m .

Для того, чтобы числа a и b были сравнимы по модулю n , представленному в виде его канонического разложения на простые сомножители p i

необходимо и достаточно, чтобы

Отношение сравнения является отношением эквивалентности и обладает многими свойствами обычных равенств. Например, их можно складывать и перемножать: если

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

Нельзя также выполнять операции со сравнениями, если их модули не совпадают.

Другие свойства:

Связанные определения

Классы вычетов

Множество всех чисел, сравнимых с a по модулю n называется классом вычетов a по модулю n , и обычно обозначается [a ] n или . Таким образом, сравнение равносильно равенству классов вычетов [a ] n = [b ] n .

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

Операции сложения и умножения на индуцируют соответствующие операции на множестве :

[a ] n + [b ] n = [a + b ] n

Относительно этих операций множество является конечным кольцом , а если n простое - конечным полем .

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

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

0,1,...,n − 1

или абсолютно наименьшие вычеты, состоящие из чисел

,

в случае нечётного n и чисел

в случае чётного n .

Решение сравнений

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

В теории чисел , криптографии и других областях науки часто возникает задача отыскания решений сравнения первой степени вида:

Решение такого сравнения начинается с вычисления НОД (a, m)=d . При этом возможны 2 случая:

• Если b не кратно d , то у сравнения нет решений.
• Если b кратно d , то у сравнения существует единственное решение по модулю m / d , или, что то же самое, d решений по модулю m . В этом случае в результате сокращения исходного сравнения на d получается сравнение:

где a 1 = a / d , b 1 = b / d и m 1 = m / d являются целыми числами, причем a 1 и m 1 взаимно просты. Поэтому число a 1 можно обратить по модулю m 1 , то есть найти такое число c , что (другими словами, ). Теперь решение находится умножением полученного сравнения на c :

Практическое вычисление значения c можно осуществить разными способами: с помощью теоремы Эйлера , алгоритма Евклида , теории цепных дробей (см. алгоритм) и др. В частности, теорема Эйлера позволяет записать значение c в виде:

Пример

Для сравнения имеем d = 2 , поэтому по модулю 22 сравнение имеет два решения. Заменим 26 на 4, сравнимое с ним по модулю 22, и затем сократим все 3 числа на 2:

Поскольку 2 взаимно просто с модулем 11, можно сократить левую и правую части на 2. В итоге получаем одно решение по модулю 11: , эквивалентное двум решениям по модулю 22: .

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

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

История

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