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

На 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: .

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

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

История

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

Рассмотрим систему сравнений

Где f1(x), f2(x), …. , fs(x)€Z[x].

Теорема 1. Пусть M = - наименьшее общее кратное чисел m1,m2,…,ms . Если а удовлетворяет системе (2), то и любое число из класса а по модулю М удовлетворяет этой системе.

Доказательство. Пусть b€ классу а. Так как а ≡ b(mod M), то а ≡b(mod m), i= 1,2,...,s (свойство сравнений 16). Следовательно, b, как и а, удовлетворяет каждому сравнению системы, что и доказывает теорему. Поэтому естественно считать решением системы (2) класс по модулю М.

Определение. Решением системы сравнений (2) называется класс чисел по модулю М = , удовлетворяющих каждому сравнению системы.

12. Сразу заметим, что нечётные числа не удовлетворяют второму сравнению. Взяв чётные числа из полной системы вычетов по модулю 12, непосредственной проверкой убеждаемся, что 2-му сравнению удовлетворяют числа 2, -2, 6, а система имеет два решения: х ≡ 2(mod l2), х ≡ -2(mod 12).

Рассмотрим систему сравнений 1-ой степени (3)

Теорема2. Пусть d=(m1,m2), М = .

Если с1 - с2 не делится на d, то система (3) не имеет решений.

Если (c1 -c2):d, то система (3) имеет одно решение - класс по модулю М.

Доказательство. Из 1-го сравнения x = c1+m1t, t€Z. Подставляем во 2-е сравнение: с1+ m1t ≡ c2(mod m2) или

m1t ≡ c2-cl (mod m2). Это сравнение имеет решение только если (с2 – с1): d.

И решение представляет собой класс по модулю (теорема 4 из §2).

Пусть решение , то есть , где k€Z.

M== , то есть x≡c1+m1t0(mod M) - решение

Примеры.

1. :2, система имеет одно решение класс по модулю 24. Из 1-го сравнения х =2+6t. Подставив вместо х во 2-е сравнение, имеем: 2 + 6t≡ 4(tnod 8); 6t≡ 2(mod 8); -2t≡2(mod8); t≡-1(mod 4); t=-1+4k; x=2+6(-1+4k); x=-4+24k, то есть x≡-4(mod 24).

2. 7-3 не делится на 3, система не имеет решений.

Следствие 1. Система сравнений (4)

Либо не имеет решений, либо имеет одно решение – класс по модулю M=.

Доказательство. Если система первых двух сравнений не имеет решений, то и (4) ие имеет решений. Если она имеет решение х ≡ a(mod), то, добавив к этому сравнению третье сравнение системы, получим снова систему вида (3), которая либо имеет одно решение, либо не имеет решений. Если имеет решение, то будем так продолжить, пока не исчерпаем все сравнения системы (4). Если решение есть, то это класс по модулю М.

Замечание. Здесь использовано свойство НОК: =.

Следствие 2 . Если m1,m2,…,ms попарно взаимно простые, то система (4) имеет одно решение - класс по модулю M=m1m2…ms.

Пример:

Так как модули попарно взаимно простые, система имеет одно решение - класс по модулю 105 = 5*3*7. Из первого сравнения

Подставляем во второе сравнение: 2 +5t≡ 0(mod 3) или 2t≡-2(mod3), t=-1+3k, x=2+5(-1+3k), x=-3+15k. Подставим в третье сравнение:

3+15k≡5(mod7), 15k≡8(mod 7), k=1+7l. тогда x=-3+15(1+7l); x=12+105l; x≡12(mod 105).

Познакомимся с другим способом решения этой системы, (Используем то, что система имеет одно решение.) Умножим обе части и модуль первого сравнения на 21, второго-на 35б третьего – на 15: из суммы первого и третьего вычтем второе:

(36 -35)х ≡ 75 + 42(modl05); x≡117(mod105); x≡12(mod105).

Рассмотрим теперь систему сравнений первой степени общего вида

Если некоторое сравнение этой системы не имеет решений, то и система не имеет решений. Если же каждое сравнение системы (5) разрешимо, то решим его относительно х и получим равносильную систему вида (4):

Где (теорема 4, §2).

По следствию 1 система либо не имеет решений, либо имеет одно решение.

Пример:

Решив каждое сравнение системы, получим равносильную систему

Эта система имеет одно решение - класс по модулю 105. Умножив первое сравнение и модуль на 3, а второе на 35, получим

Вычитая из второго сравнения первое, умноженное на 11, получаем 2х ≡-62(modl05), откуда х ≡ -31(modl05).

Задачи, сводящиеся к рассмотрению системы сравнений 1-ой степени, рассматривались в арифметике китайского математика Сун Тзу, жившего примерно в начале нашей эры. У него вопрос ставился в следующей форме- найти число, дающее заданные остатки при делении на заданные числа. Он даёт и способ решения, эквивалентный следующей теореме.

Теорема (китайская теорема об остатках). Пусть m1,m2,…,ms- попарно взаимно простые числа, М = mlm2...ms, β1, β2,…, βs подобраны так, что

Тогда решение системы

Будет иметь вид x≡x0(mod M).

Доказательство. Поскольку получим x0≡

Аналогичным образом проверяем, что x0≡c2(mod m2),…, x0≡cs(mod ms), то есть x0 удовлетворяет всем

сравнениям системы.

10. Сравнения 1-й степени. Неопределённые уравнения

§ 2. Сравнения 1-й степени. Неопределённые уравнения

Сравнение 1-ой степени может быть приведено к виду ax≡b(mod m).

Теорема 4. Если (a,m) = 1, то сравнение ах ≡b(mod m) (2) имеет единственное решение.

Доказательство. Возьмём 0,1,2,...,m-1 - полную систему вычетов по модулю m. Так как (а,m) = 1, то 0,а,2а,...,(m-1)а - тоже полная система вычетов (теорема 3, §2, гл 2.). В ней найдётся одно и только одно число, сравнимое с b по модулю m (принадлежащее тому же классу, что и b). Пусть это ах 0 , то есть ax 0 € классу b или ax 0 ≡b(mod m). x ≡x 0 (mod m) - единственное решение (2). Теорема доказана.

Теорема 5. Если (а, m)= 1, то решением сравнения ах≡b(mod m) является класс х 0 ≡a φ (m)-1 b(mod m).

Доказательство. Так как (a,m) = 1, то по т. Эйлерa а φ(m) ≡1(mod m). Легко видно, что x 0 ≡a φ (m)-1 b (mod m)- решение сравнения (2). Действительно,a(a φ (m)-1 b)≡a φ (m) b≡b(mod m). Из теоремы 4 следует, что это решение единственное.

Рассмотрим методы решений сравнения ах ≡b(mod m).

1. Метод подбора. Взяв полную систему вычетов по модулю m, выбираем числа, удовлетворяющие сравнению.

2. Использование теоремы Эйлера (теорема 5).

3. Метод преобразования коэффициентов. Надо попытаться преобразовать коэффициенты так, чтобы правую часть можно было бы разделить на коэффициент при х. Преобразования, о которых идёт речь, следующие: замена коэффициентов абсолютно наименьшими вычетами, замена числа b сравнимым по модулю числом (прибавлением числа, кратного модулю) с тем, чтобы последнее делилось на а, переход от а и b к другим, сравнимым с ними числам, у которых оказался бы общий делитель и т.п. При этом пользуемся свойствами сравнений и основанными на них теоремами о равносильных сравнениях.

1) 223x ≡ 115(mod ll).

Сначала заменим коэффициенты наименьшими по абсолютной величине вычетами: Зх ≡ 5(mod 11). Если воспользоваться теоремой

Эйлера, то

х≡3 φ(11)-1 *5=3 9 *5≡(3 3) 3 *5≡(27) 3 *5≡5 3 *5≡125*5≡4*5≡9(modll).

Однако проще преобразовать коэффициенты. Заменим сравнение равносильным, прибавив к правой части число, кратное модулю:

3x ≡ 5 + 22(mod 11). Разделив обе части на число 3, взаимно простое с модулем, получим х ≡ 9(mod l1).

2) 111x≡ 8(mod 34).

Используем метод преобразования коэффициентов.

(111-3*34)x≡8(mod 34), 9x≡8+34≡42(mod 34), 3x≡14(mod 34), 3x≡14+34≡48(mod 34), x≡16(mod 34).

Теорема 6. Если (a, m) = d и b не делится на d, то сравнение (1) не имеет решений.

Доказательство (от противного). Пусть класс x 0 - решение, то есть ax 0 ≡b (mod m) или (ax 0 -b):m, а, следовательно, (ax 0 -b):d. Но a:d, тогда иb:d - противоречие. Следовательно, сравнение не имеет решений.

Теорема 7. Если (a,m)= d, d>1, b:d, то сравнение(1) имеет d

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

Где с удовлетворяет вспомогательному сравнению

Замечание. Согласно теореме сравнение (1) решается следующим образом.

1) Убедившись, что (a,m) = d, d> 1 и b:d, делим обе части в сравнения (2) на d и получаем вспомогательное сравнение a 1 x≡b 1 (mod m 1) , где . Сравнение имеет единственное решение. Пусть класс с – это решение.

2) Записываем ответ x 0 ≡c(mod m), x 1 ≡c+m 1 (mod m), x 2 ≡c+2m 1 (mod m), … , x d -1 ≡c+(d-1)m 1 (mod m).

Доказательство. Вспомогательное сравнение по теореме 2(3) равносильно исходному сравнению (2). Так как ( 1, То вспомогательное сравнение имеет единственное решение – класс по модулю m 1 = . Пусть x≡c(mod m 1) – это решение. Класс чисел с по модулю m 1 распадается на d классов по модулю m: .

Действительно, любое число из класса х0 по модулю m 1 имеет вид x 0 +m 1 t. Разделим t с остатком на d: t = dq +r, где 0≤r

Итак, сравнение (1) имеет d решений по модулю m: х0 , x0+m1,..., х0 +(d-1)m1.(сверху черточки горизонтальные)

Примеры.

1) 20x≡ 15(mod 108). Так как (20,108) = 4 и 15 не делится на 4, то решений нет.

2) 20x≡ 44(mod 108). (20,108) = 4 и 44:4, следовательно, сравнение имеет четыре решения. Разделив обе части и модуль на 4,получим:

5х≡11(mod 27); 5 x≡11-81 ≡ -70(mod27), х ≡ -14 ≡ 13(mod 27). Тогда х≡13 + 27r(mod 108), где г= 0,1,2,3. I jj

Ответ: x≡13(modl08); х ≡ 40(modl08); х ≡ 67(modl08); x≡94(modl08).

Применение теории сравнений к решению неопределённых уравнении

Рассмотрим неопределённое или, как его иначе называют, Диофантово уравнение первой степени с двумя неизвестными ах + by = с, где a,b,c€Z. Требуется решить это уравнение в целых числах. Если (a,b)=d и с не делится на d, то очевидно, чТО сравнение не имеет решений в целых числах. Если же с делится на d, ТО поделим обе части уравнения на d. Поэтому достаточно рассмотреть случай, когда (а, b) =1.

Так как ах отличается от с на число, кратное b, то ах ≡ c(mod b) (без ограничения общности можно считать, что b > 0). Решая это сравнение, получим х ≡x1 (mod b) или x=x1+bt, где t€Z. Для определения Соответствующих значений у имеем уравнение а(х1 + bt) + by = с, откуда

Причём -целое число, оно является частным значением неизвестного y, соответствующим x1(получается, как и x1, при t=0). А общее решение уравнения примет вид систему уравнений x=x1+bt, y=y1-at, где t- любое целое число.

Заметим , что 1) уравнение ах + by = с можно было решать, начав со сравнения by ≡ c(mod а), так как by отличается от с на число, кратное а;

2)в качестве модуля удобнее выбирать наименьший из модулей а и b.

Пример , 50x – 42y= 34.

Разделим обе части уравнения на 2.

25х ≡ 17(mod2l); 4х ≡ 17 (mod 21) или 4х ≡ 17-21 ≡ -4(mod21).

х ≡ -1 (mod 21), то есть x=-1+21t, t€Z. Подставим найденное х в уравнение. 25(-1 + 21t)- 21y= 17; 21у =-42 + 25* 21t и у =-2 + 25t.

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

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 с операцией называется группой , если удовлетворяются следующие условия.

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

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

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

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

(2)

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

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

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

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

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

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

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

Примеры 25≡39 (mod 7), −18≡14 (mod 4).

Из первого примера следует, что 25 при делении на 7 дает тот же остаток, что и 39. Действительно 25=3·7+4 (остаток 4). 39=3·7+4 (остаток 4). При рассмотрении второго примера нужно учитывать, что остаток должен быть неотрицательным числом, меньшим, чем модуль (т.е. 4). Тогда можно записать: −18=−5·4+2 (остаток 2), 14=3·4+2 (остаток 2). Следовательно −18 при делении на 4 дает остаток 2, и 14 при делении на 4 дает остаток 2.

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

Свойство 1. Для любого a и p всегда

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

где λ это наибольший общий делитель чисел m и p .

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

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

Следовательно

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

где h=pqs.

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

Два целых числа а и в сравнимы по модулю натурального числа m є N, если при делении на m они дают одинаковый остаток. .

Теорема (критерий сравнимости): . Следствие 1 : каждое число сравнимо по модулю m со своим остатком от деления на m: . Следствие 2: число сравнимо по модулю m, т. и т. т., к. оно делится на этот mod.

Основные свойства сравнения: 1). Относительные сравнения являются относительно эквивалентными. 2). Сравнения по одному и тому же модулю можно почленно вычитать: . Слагаемое можно переносить из одной части в другую, при этом знак меняем на противоположный. 3). В каждой части сравнения можно прибавлять любое число, кратное модулю: сравнения по одному и тому же модулю можно почленно умножать. Следствия: 1. Обе части сравнения можно возводить в любую натуральную степень. 2. Обе части сравнения можно умножать на любое натуральное число. 4). Обе части сравнения и модуль можно умножить на одно и то же число или сократить на любой их общий делитель. 5). Если сравнение имеет место по нескольким модулям то оно имеет место и по модулю, который равен их наибольшему кратному или наибольшему общему делителю

6). Если сравнение имеет место по модулю m, то оно имеет место и по любому

делителю числа m. 7). Общий делитель одной части сравнения и модуль является делителем другой части сравнения: , .

Малая теорема Ферма: если a и m – взаимнопростые числа, тогда . Функция Эйлера – это число положительных чисел, не превосходящие n и взаимнопростые с n. Если целое число a взаимнопростое с m, то . Теорема Эйлера : если целое число a взаимнопростое с m, то . Теорема Ферма: 1. Если целое число a не делит p, где р – простое, то . 2. Если р – простое и а –любое целое число, тогда . Отношение сравнимости – это классы эквивалентности. Классы эквивалентности также называются классами вычетов, а их эквивалентности называют вычетами.

Решение сравнений: Пусть , , mєN. Тогда называется сравнением к – степени с одним неизвестным и имеет не более, чем m классов решений. Решениями данного сравнения будут являться классы вычетов по модулю m. Сравнения первой степени с одной неизвестной можно записать в виде: если: 1). это сравнение не имеет решения (например 5x ). 2). Если решение этого сравнения. 3). .

Теорема: Пусть , , то , d – класов решений mod m. Методы решения сравнений: 1). Метод испытания полной системы вычетов. 2). Метод преобразования коэффициентов. Прибавляется или вычитается из правой части любое число, кратное модулю, заменяя коэффициенты в левой части на число сравнений с модулем. Можно преобразовать сравнения так, что его можно будет сократить на а и получить решение.