Меню

Сравнения по простому модулю примеры



Сравнение чисел по модулю

Определение 1. Если два числа 1 ) a и b при делении на p дают один и тот же остаток r, то такие числа называются равноостаточными или сравнимыми по модулю p.

Утверждение 1. Пусть p какое нибудь положительное число. Тогда всякое число a всегда и притом единственным способом может быть представлено в виде

где s — число, и r одно из чисел 0,1, . p−1.

1 ) В данной статье под словом число будем понимать целое число.

Действительно. Если s получит значение от −∞ до +∞, то числа sp представляют собой совокупность всех чисел, кратных p. Рассмотрим числа между sp и (s+1)p=sp+p. Так как p целое положительное число, то между sp и sp+p находятся числа

Но эти числа можно получить задав r равным 0, 1, 2. p−1. Следовательно sp+r=a получит всевозможные целые значения.

Покажем, что это представление единственно. Предположим, что p можно представить двумя способами a=sp+r и a=s1p+r1. Тогда

(2)

Так как r1 принимает один из чисел 0,1, . p−1, то абсолютное значение r1r меньше p. Но из (2) следует, что r1r кратно p. Следовательно r1=r и s1=s.

Число r называется вычетом числа a по модулю p (другими словами, число r называется остатком от деления числа a на p).

Утверждение 2. Если два числа a и b сравнимы по модулю p, то a−b делится на p.

Действительно. Если два числа a и b сравнимы по модулю p, то они при делении на p имеют один и тот же остаток p. Тогда

где s и s1 некоторые целые числа.

Разность этих чисел

(3)

делится на p, т.к. правая часть уравнения (3) делится на p.

Утверждение 3. Если разность двух чисел делится на p, то эти числа сравнимы по модулю p.

Доказательство. Обозначим через r и r1 остатки от деления a и b на p. Тогда

По утверждению a−b делится на p. Следовательно rr1 тоже делится на p. Но т.к. r и r1 числа 0,1. p−1, то абсолютное значение |rr1| Свойство 1. Для любого a и p всегда

a≡a mod (p).

Свойство 2. Если два числа a и c сравнимы с числом b по модулю p , то a и c сравнимы между собой по тому же модулю, т.е. если

a≡b mod (p), b≡c mod (p).
a≡c mod (p).

Действительно. Из условия свойства 2 следует a−b и b−c делятся на p. Тогда их сумма a−b+(b−c)=a−c также делится на p.

a≡b mod (p) и m≡n mod (p),
a+m≡b+n mod (p) и a−m≡b−n mod (p).

Действительно. Так как a−b и m−n делятся на p, то

(a−b)+ (m−n)=(a+m)−(b+n) ,
(a−b)−(m−n)=(a−m)−(b−n)

также делятся на p.

Это свойство можно распространить на какое угодно число сравнений, имеющих один и тот же модуль.

a≡b mod (p) и m≡n mod (p),
am≡bn mod (p).

Действительно.Так как a−b делится на p, то (a−b)m также делится на p, следовательно

am≡bm mod (p).

Далее m−n делится на p, следовательно b(m−n)=bm−bn также делится на p, значит

bm≡bn mod (p).

Таким образом два числа am и bn сравнимы по модулю с одним и тем же числом bm, следовательно они сравнимы между собой (свойство 2).

a≡b mod (p).

где k некоторое неотрицательное целое число.

Действительно. Имеем a≡b mod (p). Из свойства 4 следует

a·a≡b·b mod (p).
a·a·a≡b·b·b mod (p).
.
a k ≡b k mod (p).

Все свойства 1-5 представить в следующем утверждении:

Утверждение 4. Пусть f(x1, x2, x3, . ) целая рациональная функция с целыми коэффициентами и пусть

a1b1, a2b2, a3b3, . mod (p).
f(a1, a2, a3, . )≡f(b1, b2, b3, . ) mod (p).

При делении все обстоит иначе. Из сравнения

am≡bm mod (p)

не всегда следует сравнение

a≡b mod (p).

Утверждение 5. Пусть

am≡bm mod (p),
a≡b mod (p/λ),

Доказательство. Пусть λ наибольший общий делитель чисел m и p. Тогда

m=m1λ и k=k1λ.

Так как m(a−b) делится на k, то

имеет нулевой остаток. Тогда

.

имеет нулевой остаток, т.е. m1(a−b) делится на k1. Но числа m1 и k1 числа взаимно простые. Следовательно a−b делится на k1=k/λ и, тогда, a≡b mod (p/λ).

Утверждение 6. Если

a≡b mod (p)

и m является один из делителей числа p, то

a≡b mod (m).

Действительно. a−b делится на p. p делится на m. Следовательно a−b делится на m.

Утверждение 7. Если

a≡b mod (p), a≡b mod (q), a≡b mod (s)
a≡b mod (h),

где h наименьшее общее кратное чисел p,q,s.

Действительно. Разность a≡b должна быть числом, кратным p,q,s. и, следовательно должна быть кратным h.

В частном случае, если модули p,q,s взаимно простые числа, то

a≡b mod (h),

Заметим, что можно допустить сравнения по отрицательным модулям, т.е. сравнение a≡b mod (p) означает и в этом случае, что разность a−b делится на p. Все свойства сравнений остаются в силе и для отрицательных модулей.

Источник

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

Пусть р – простое число, и пусть задано сравнение вида f(x)≡0(mod p), где f(x)=ax n +a1x n —1 +…+an *. Тогда справедлива

Теорема 1:

Сравнение вида * равносильно сравнению степени, не выше р—1.

Так как x p —x≡0(mod p), то f(x)≡R(x)(mod p), а степень многочлена R(x) не выше, чем р–1. Что и требовалось доказать.

Теорема 2

Если сравнение * имеет более n решений, то все коэффициенты многочлена f(x) кратны р.

Тогда многочлен f(x) можно представить в виде

Справедливость этого равенства проверяется раскрытием скобок в правой части.

Полагая в этом равенстве x=x1, убеждаемся, что p\m, полагая x=x2 и учитывая, что p\m, убеждаемся, что р\l. Полагаем, что x=x3, x=x4, …, x=xn+1 и последовательно убеждаемся, что p\c, p\b, p\a, то есть все коэффициенты из ** делятся на p.

Учтем, что a=a, , , … , , то есть коэффициенты из * являются линейными комбинациями коэффициентов из **, а значит a, a1, a2, …, an кратны р как линейные комбинации чисел, кратных р.

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

Теорема

** ,

Равносильность сравнения и системы очевидна и следует из свойств 12 и 13 сравнений.

Утверждение о количестве решений следует из того, что каждое сравнение

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

А решение сравнение вида f(x)≡0(mod p α ) может быть найдено, если известно решение сравнения f(x)≡0(mod p). Покажем это.

Пусть x≡x1(mod p) – решение сравнения f(x)≡0(mod p). Тогда x можно представить в виде

x=x1+pt1, где .

Читайте также:  Как можно сравнить 2 региона

Подставляя такое x в сравнение f(x)≡0(mod p 2 ) и применяя формулу Тейлора (учитывая, что f(x) – многочлен, x1 – целое число, поэтому ), получаем

Поскольку f(x1)≡0(mod p), то p\f(x1), а значит можно сократить в получившемся выражении на p правую, левую части и модуль. Получим:

Если f ‘(x1) не делится на р, то данное сравнение имеет одно решение:

(т.е. )

Подставляя полученное x в сравнение f(x)≡0(mod p 3 ), имеем

откуда, сократив правую, левую части и модуль на p 2 , получим

Тогда сравнение имеет одно решение , или, что то же самое, , откуда получаем решение по модулю p 3 : x=x3+p 3 t3.

Продолжим этот процесс до тех пор, пока не будет решено сравнение по модулю p α . Итак, по данному решению сравнения f(x)≡0(mod p) можно найти решение сравнения f(x)≡0(mod p α ).

Требуется решить сравнение x 3 +9x—1≡0 (mod 125).

Известно, что сравнение x 3 +9x—1≡0 (mod 5) имеет одно решение:

Поскольку модуль «5» небольшой, а общих подходов к сравнениям высоких степеней мы пока не знаем, то этот корень нашли простым перебором, попутно убедившись в его единственности.

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

Решим это сравнение.

Или, что то же самое, t1=0+5t2, откуда решение по модулю 25 есть x=2+25t2. Подставим полученное x в сравнение по модулю 125:

Решим это сравнение.

Получили сравнение первой степени. Решим его. Отыщем 3 -1 (mod 5), для чего, как всегда, воспользуемся расширенным алгоритмом Евклида:

Тогда решением сравнения относительно t2 будет

Источник

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

Содержание

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

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

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

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

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

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

  • 1. Два числа, сравнимые с третьим сравнимы между собой. [math]a \equiv c(mod \text< >m) \text <, >b \equiv c(mod \text< >m) \Rightarrow a \equiv b(mod \text< >m)[/math]
    • Легко выводится из пункта «а».
  • 2. Сравнения можно почленно складывать. [math] a_1 + a_2 + a_3 \equiv b_1 + b_2 + b_3(mod \text< >m)[/math]
    • Представляем сравнения, как в пункте «а» и складываем.
  • 3. Сравнения можно почленно перемножать. [math] a_1a_2a_3 \equiv b_1b_2b_3(mod \text< >m)[/math]
    • Представляем сравнения, как в пункте «а», перемножаем, получим [math] a_1a_2a_3 = b_1b_2b_3+mN[/math] , где N—целое.
  • 4. Обе части сравнения можно разделить на их общий делитель, если последний взаимно прост с модулем.
    • Действительно, из [math]a \equiv b(mod \text < >m)[/math] , [math] a = a_1d, b = b_1d, (d,m)=1[/math] следует, что [math] a-b = (a_1 — b_1)d \vdots m [/math] , поэтому [math] a_1 \equiv b_1(mod \text < >m)[/math] .
  • 5. Обе части сравнения можно умножить на одно и тоже число.
    • Действительно, из [math]a \equiv b(mod \text < >m)[/math] , следует [math] a = b+mt, ak =bk +mkt [/math] , и, следовательно, [math]ak \equiv bk(mod \text < >mk)[/math] .
  • 6. Обе части сравнения и модуль можно разделить на их общий делитель.
    • Действительно, пусть [math]a \equiv b(mod \text < >m), a = a_1d, b=b_1d, m=m_1d[/math] , отсюда [math] a= b+mt, a_1d =b_1d +m_1dt, a_1 =b_1 +m_1t[/math] , и, следовательно, [math]a_1 \equiv b_1(mod \text < >m_1)[/math] .
  • 7. Если сравнение [math]a\equiv b[/math] имеет место по нескольким модулям, то оно имеет место и по модулю равному НОК этих модулей.
    • В самом деле, из [math] a \equiv b(mod \text< >m_1),\ldots,a \equiv b(mod \text< >m_k)[/math] следует, что разность [math] a-b [/math] делится на все модули [math] m_1,m_2,\ldots,m_k[/math] . Поэтому она должна делиться и на их НОК.
  • 8. Если сравнение имеет место по модулю m, то оно имеет место и по модулю d, равному любому делителю числа m.
    • Следует из пункта «б».
  • 9. Если одна часть сравнения и модуль делятся на некоторое число, то и другая сторона сравнения должна делиться на это число.
    • Следует из пункта «а».
  • 10. Если [math]a \equiv b(mod \text< >m) [/math] , то [math](a,m) = (b,m) [/math] .
    • Следует из пункта «а» по свойству НОДа.

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

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

Любое число класса называется вычетом по модулю m. Вычет получаемый при [math] t = 0[/math] , равный самому остатку r, называется наименьшим неотрицательным вычетом.

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

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

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

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

Пример 1.
[math] 12x \equiv 6(mod \text< >18)[/math]
Найдем НОД [math](12,18)=6 [/math]
Перейдем к новому сравнению [math] 2x \equiv 1(3) [/math]
Легко находится [math] x_0 = 2 [/math]
Тогда ответом будет [math] x_0 =2, x_1 = x_0 — \frac<(a,m)>=-1, x_2 = -4[/math]

Пример 2.
[math] 111x \equiv 75(mod \text< >321)[/math]
Найдем НОД [math](111,321)=3 [/math] , 75 кратно 3, значит имеем 3 решения
Перейдем к новому сравнению [math] 37x \equiv 25(107) [/math]
Воспользуемся цепными дробями, в нашем случае [math] n=4, p_ = 26[/math] , значит [math] x_0 \equiv -26\cdot 25 (107) \equiv 99(107) [/math]
Тогда ответом будет [math] x_0 = 99, x_1 = 206, x_2 = 313 [/math] .

Источник