Пункт 19. Порівняння першого степеня.
У наступних трьох пунктах навчимося розв’язувати порівняння з одним невідомим виду:
f(x) º 0(mod m),
де f(x)=a0 xn +a1 xn-1 +...+an-1 x+an – многочлен з цілими коефіцієнтами. Якщо m не ділить a0, то говорять, що n – ступінь порівняння. Зрозуміло, що якщо яке-небудь число х підходить для порівняння, то для цього ж порівняння підійде і будь-яке інше число, порівняльне з х за mod m.
Розв’язати порівняння – означає знайти всі ті х, що задовольняють даному порівнянню, при цьому весь клас чисел за mod m вважається одним розв’язком.
Таким чином, число розв’язків порівняння є числом лишків з повної системи, що цьому порівнянню задовольняють.
Приклад. Дано порівняння: x5 +x+1 º 0(mod 7)
З чисел: 0, 1, 2, 3, 4, 5, 6, це порівняння задовольняють два: x1 =2, x2 =4. Це означає, що в даному порівнянні два розв’язки:
x º 2(mod 7) і x º 4(mod 7) .
Порівняння називаються рівносильними, якщо вони мають однакові розв’язки – повна аналогія з поняттям рівносильності рівнянь. Однак, на відміну від алгебраїчних рівнянь, що часто нерозв'язуються радикалами, порівняння будь-якого ступеня завжди розв’язується, наприклад, перебором усіх лишків за mod m. Перебір і підставлення всіх лишків - найчастіше дуже довгий процес (особливо, при великих m і n), але і тут існують набори інструкцій, виконуючи які можна завжди знайти всі розв’язки даного порівняння будь-якого степеня, минаючи процес перебору.
Розглянемо порівняння першого степеня виду axº b(mod m), (два випадки).
Випадок 1. Нехай а і m взаємно прості. Тоді нескоротний дріб m/a розкладається в ланцюговий дріб:
Цей ланцюговий дріб, зрозуміло, скінченний, тому що m/a - раціональне число. Розглянемо два останні прямуючі дроби:
; 
Згадуємо (пункт 9) властивість чисельників і знаменників прямуючих дробів: mn-1-an-1=
=(-1)n. Далі (доданок mn-1, кратний m, можна викинути з лівої частини порівняння):
-an-1 º (-1)n (mod m) тобто
an-1 º (-1)n-1 (mod m) тобто
a[(-1)n-1 Pn-1 b] º b(mod m)
і єдиним розв’язком вихідного порівняння є:
x º (-1)n-1 Pn-1 b(mod m)
Приклад. Розв’язати порівняння 111x º 75(mod 322).
Розв’язування. (111, 322)=1. Включаємо алгоритм Евкліда:
322=11 · 2+100
111=100 · 1+11
100=11 · 9+1
11=1 · 11
(У рівностях підкреслені неповні частки.) Виходить, n=4, а відповідний ланцюговий дріб:
Порахуємо чисельники прямуючих дробів, склавши для цього стандартну таблицю:
|
|
0 |
2 |
1 |
9 |
11 |
|
P n |
1 |
2 |
3 |
29 |
322 |
Чисельник передостаннього прямуючого дробу дорівнює 29, отже, маємо відповідь:
x º (-1)3 × 29 × 75 º -2175 º 79(mod 322)
Іншими словами, дано порівняння ax º b(mod m), де a і m взаємно прості. Візьмемо алгоритм Евкліда і знайдемо u, v Î Z такі, що au+vm=1. Помножимо цю рівність на b: aub+vmb=b, звідки випливає: aub º b(mod m). Отже розв’язком вихідного порівняння є xº ub(mod m).
Теорема 2. Нехай m>1, (a,m)=1 Тоді порівняння axº b(mod m) має розв’язок:
xºbaj(m)-1(mod m).
Доказ. За теоремою Ейлера, маємо: aj(m)º 1(mod m), отже, a× baj(m)-1º b(mod m).
Приклад. Розв’язати порівняння 7xº 3(mod 10). Обчислюємо:
j(10)=4; xº 3 × 74-1 (mod 10) º 1029(mod 10) º 9(mod 10).
Цей спосіб розв’язування порівнянь гарний, але може зажадати піднесення числа а до великого степеня.
Теорема 3. Нехай р – просте число, 0<a<p. Тоді порівняння axº b(mod p) має розв’язок:
де Ca p – біноміальний коефіцієнт.
Доказ випливає з очевидного порівняння
яке необхідно почленно поділити на взаємно просте з модулем число 1 × 2 × 3 × ... × a-1.
Приклад. Розв’язати порівняння 7x º 2(mod 11) . Обчислюємо:
Перейдемо до систем порівнянь першого степеня.
