ртається в нуль, а - 1) порівнянно з нулем за теоремою Ферма (х і р взаємно прості, так як х <р). Це означає, по лемі 2, що всі коефіцієнти виписаного порівняння крани р, зокрема, на р. ділиться його вільний член, рівний 1 * 2 * 3 * ... * (р - 1) + 1. p> Повернутись. Якщо р - не просте, то знайдеться дільник d числа р, l
(р - 1) + 1 0 (mod p) не виконується.
.2 Випадок складеного модуля.
Порівняння
(1)
де - довільний многочлен з цілими коефіцієнтами,
, n> 1 і попарно прості, рівносильне системі:
(2)
Зауваження. Число рішень порівняння (1) дорівнює добутку числа рішень кожного з порівнянь системи (2). Якщо хоча б одне з порівнянь системи (2) не має рішень, то система несумісна і, отже, порівняння (1) не має рішень. p> Порівняння виду
()
де - цілі позитивні, а - прості числа, також рівносильне системі:
()
Вирішення цієї системи зводиться до вирішення порівнянь виду
, (3)
вирішення якої, у свою чергу, починається з рішення порівнянь
. (4)
Шляхом безпосередніх випробувань відрахувань по модулю p знаходяться всі рішення порівняння (4). Нехай
В
- (5)
одне з рішень порівняння (4). Для цього рішення складається порівняння
В
(- перша похідна функції f (x) при), з якого знаходиться, або (при, що не делящимся на p). Після підстановки значення в рівність (5) знаходимо:
. (6)
Далі вирішується порівняння, з якого знаходимо або, і після підстановки в (6) отримаємо:
. (7)
Обчислення продовжуємо до тих пір, поки не отримаємо, або
. (8)
Рішення (8) і є рішенням порівняння (3).
Якщо виявиться, що ділиться на р, то рішення для не буде, отже, і рішення (5) не буде вирішенням порівняння (3).
Практична частина
1) Замінити порівняння - 10х + 13 0 (mod 59)
еквівалентним порівнянням з коефіцієнтом при старшому члені, рівним 1.
Рішення.
Вирішуємо порівняння 27 січня (mod 59) і знаходимо = 35. Дане нам порівняння еквівалентно порівнянні
0 (mod 59),
т. е. порівнянні 0 (mod 59).
Відповідь. 0 (mod 59). br/>
2) Порівняння 0 (mod 7)
замінити еквівалентним порівнянням ступеня, меншою, ніж 7.
Рішення.
Замінимо на =, на, на х. Таким чином, задане порівняння еквівалентно порівнянні
0 (mod 7),
т. е. порівнянні 0 (mod 7).
Відповідь. 0 (mod 7). br/>
3) = 31 задовольняє порівнянні 11 65 (mod 103).
Знайт...
