| 3 | 0 | 3 | 2 | 0 | 1 | |
| 2 | 3 | 6≡1 | 5≡0 | 2 | 4 | 9≡4 |
| -2 | 3 | 6≡ -1 | 5≡0 | 2 | -4 | 9≡4 |
Отже, конгруенція Зх5 + 3x3 + 2x2 +1 ≡ 0 (mod 5) не має розв'язків, а тому не має розв'язків і конгруенція
8x5 — 12x3 — 13x2 — 15x + 6 ≡ 0 (mod 5).
При розв'язуванні конгруенції з невідомою величиною іноді доводиться множити обидві частини конгруенції на ціле число. Для тотожних конгруенцій ця операція, як раніш було показано, завжди законна. Для конгруенцій з невідомою величиною таке перетворення не завжди законне, тобто, інакше кажучи, при такому перетворенні конгруенції може порушитись еквівалентність даної і добутої конгруенцій.
Приклад. Конгруенція
x4 + х3 + х2 + х + 1 ≡ 0 (mod5),
як ми вище бачили, має один розв'язок: x ≡ 1 (mod5). Але, якщо обидві частини цієї конгруенції помножити на 5, то дістанемо конгруенцію:
5x4 + 5х3 + 5х2 + 5х + 5 ≡ 0 (mod5),
розв'язком якої буде вже будь-яке ціле число. Вона, по суті,перетворюється в конгруенцію 0 ≡ 0 (mod 5).
Конгруенції виду 0 ≡ 0 (mod 5) мають очевидно розв'язком будь-яке ціле значення невідомого х, тобто є тотожною конгруенцією.
Після наведеного щойно прикладу виникає питання, коли множення обох частин конгруенції з невідомою величиною на ціле число є законним? Відповідь на це дає теорема 2.
Теорема 2. Якщо обидві частини конгруенції (1) помножити на ціле число k, взаємно просте з модулем т, то дістанемо конгруенцію, еквівалентну даній.
Справді, припустимо, що
х = α (modт)
є який-небудь розв'язок конгруенції (1), тоді
f (α) ≡ 0 (modm).
Помножаючи обидві частини цієї конгруенції на k, дістанемо:
k∙f (α) ≡ 0 (modm). (2)
Отже, ми бачимо, що α є розв'язком конгруенції
k∙f (x) ≡ 0 (modm). (3)
Навпаки, якщо α — розв'язок конгруенції (3), тобто k∙f (α) ≡ 0 (modm), тоді обидві частини конгруенції (2) можна скоротити на k, не змінюючи модуля, бо (k, m) = 1, (див. властивість 4, п.1.1), отже,
f (α) ≡ 0 (modm),
тобто α є розв'язком конгруенції (1), що і доводить наше твердження.
Зауважимо, що при розв'язуванні конгруенцій з невідомою величиною можна, не змінюючи модуля, скорочувати обидві частини конгруенції тільки на такий їх спільний дільник, який є взаємно простий з модулем (див. властивість 4, п.1.1).
2.2. Конгруенції n-го степеня за простим модулем.
У попередньому параграфі ми бачили, що дослідження й розв'язання конгруенції п-го степеня (п≥1) зводиться кінець кінцем до дослідження і розв'язання відповідних конгруенцій за простими модулями. Тому зараз доведемо деякі загальні теореми, що стосуються конгруенцій n-го степеня за простим модулем р.
Припустимо, що задано конгруенцію[1]:
f(х)= а0хп + а1хп-1 + . . . + аn-1x + an ≡ 0 (mod p), n≥1, (1)
де a0≠0 (modp) і р — просте число.
Теорема 1. Конгруенцію (1) завжди можна так перетворити що її старший коефіцієнт дорівнюватиме одиниці.
Справді, через те що р — просте і a0 не ділиться на р, то завжди існує єдине число α, що а0α ≡ 1 (modp). Помноживши тепер конгруенцію (1) на α і замінивши а0x одиницею, дістанемо еквівалентну конгруенцію з старшим коефіцієнтом, що дорівнює одиниці:
xn + b1xn-1+ .. + bn-1x + bn≡ 0 (modp); (1')
тут bi ≡ aiα (modp).
Теорема 2. Якщо степінь конгруенції (1) не менший від модуля конгруенції, то вона еквівалентна деякій конгруенції степеня, не вище за р—1 (за тим самим модулем).
Справді, поділимо f(х) на хр-х; і частку від ділення позначимо через q(x), а остачу через r(х). Тоді на підставі алгоритму ділення з остачею дістанемо:
f(x) = (xp—x)q(x) + r(x),
де частка q(х) і остача r(х) будуть многочленами з цілими коефіцієнтами, причому степінь r(х) буде не вище р—1. За теоремою Ферма xp—-x ≡ 0 (modp) при будь-якому цілому х, тому дістанемо тотожну конгруенцію:
f(х) ≡ r(x) (mod р).
Ця тотожна конгруенція показує, що корені конгруенції (1) і конгруенції r(х)≡0 (mod р) однакові. Оскільки хр — х завжди ділиться на p, то f(x) і r(x) можуть ділитись на pтільки одночасно; отже, конгруенції
f(х) ≡ 0 (mod р) і r(х) ≡ 0 (mod р)
еквівалентні. Через те що степінь r(x) менше за p, то теорему доведено.
Зокрема, може статись, що f(x) ділиться на xp—-x , тобто r(х) ≡ 0 (mod р) – тотожна конгруенція за модулем p, тобто остача при діленні конгруентна з нулем і дана конгруенція еквівалентна конгруенції 0 ≡ 0 (modp) та справедлива при будь-якому цілому x. Далі, нехай остача від ділення f(х) на xp—-x є многочлен нульового степеня, що дорівнює bp-1. Якщо bp-1 не ділиться на p, то дана конгруенція не має розв’язків, бо вона зводиться до невірної конгруенції :
bp-1 ≡ 0 (modp).
Приклад. Якій конгруенції нижче від 5-го степеня еквівалентна конгруенція:
f(х) = х17 + 2x11 + Зx8 — 4x7 + 2x — 3 ≡ 0 (mod5).
Поділивши f (х) на х5 — х і замінивши всі коефіцієнти остачі найменшими невід'ємними лишками за модулем 5, дістанемо, що дана конгруенція еквівалентна конгруенції
r(х) = Зx4 + Зx3 + Зx + 2 ≡ 0 (mod 5).
Зауваження. Можна вказане ділення на хp — х фактично і не виконувати, а просто замінити хn на хr, де r > 0 є остача від ділення п на р — 1. Справді, за теоремою Ферма хр ≡ х (mod р), звідси xp+1 ≡ x2, xp+2 ≡ x3, ... і взагалі:
Через те що в нашому прикладі x17 можна замінити через х, а 2x11 через 2x3, Зx8 через Зx4,—4x7 замінити через —4x3 ≡ x3 , тому відразу дістанемо:
f(x) ≡ Зx4 + Зx3 + Зx + 2 ≡ 0 (mod 5).
У свою чергу, останню конгруенцію можна спростити так: х ≠ 0 (mod5), тому x5-1 ≡ 1 (mod5) і
f(x) ≡ Зх3 + Зх ≡ 0 (mod 5),
або
f(x) ≡ х2 + 1 ≡ 0 (mod 5).
Очевидні розв'язки останньої конгруенції x ≡ 2, 3 (mod 5) будуть також і розв'язками даної конгруенції:
f(x) ≡ 0 (mod 5).
Теорема 3. Якщо α1—який-небудь розв'язок конгруенції (1), то має місце тотожна конгруенція:
f(х) ≡ (х — α1)f1(х) (modр), (2)
де f1(х) — многочлен степеня, на одиницю нижчий від степеня многочлена f(x). Старший коефіцієнт многочлена f1(x) збігається з старшим коефіцієнтом даного многочлена fix).
Справді, поділимо f(x) на х — α1і частку позначимо через f1(х), а остачу через r. За теоремою Безу r = f(α1), але
f(α1) ≡ 0 (mod p)
за умовою, тоді конгруенцію
f(x) = (x – α1) f1(x) + f(α1) ≡ 0 (mod р)
можна переписати так:
f(x) ≡ (x-α1)f1(x) (modp).
При цьому кажуть, що f(х) ділиться на х — α1 за модулем р. Очевидно, що й навпаки: з конгруенції (2) випливає, що f(α1) ≡ 0 (modp) тобто α1 — корінь конгруенції (1); отже, маємо такий висновок.
Висновок. Конгруенція (1) має корінь х = α1тоді і тільки тоді, коли ліва її частина f(x) ділиться на х — α1 за даним модулем р.
Зауважимо, що теорема 3 і висновок з неї справедливі і для складеного модуля т.
Теорема 4. Якщо α1, α2, . . , αk (k ≤n) є різні розв'язки конгруенції (1), то має місце тотожна конгруенція:
f(х) ≡ (х – α1) (х - α2) . . . (х - αk) fk (x) (modp), (3)
де степінь f (х) дорівнює п — k і старші коефіцієнти у f(x) і fk(x) однакові.
Справді, згідно, з теоремою 3 конгруенція (1) еквівалентна конгруенції
(x - α1)f1(x) ≡ 0 (modp). (21)
Через те що α2 є розв'язок конгруенції (1), то, підставляючи його в еквівалентну конгруенцію (2'), дістанемо тотожну конгруенцію:
(α2 — α1)f1(α2) ≡ 0 (mod р).
Але добуток двох чи кількох чисел ділиться на просте число р тоді і тільки тоді, коли на р ділиться принаймні один з співмножників. За умовою α1 і α2 різні, тобто
α1≠α2 (modp),
отже, α2 — α1 не ділиться на р, а тому f1(α2) ділиться на р, тобто f1(α2) ≡ 0 (mod p); останнє означає, що α2 — розв'язок конгруенції f1(x)≡0 (mod p). За теоремою 3 дістанемо:
f1(х)≡ (x-α2)f2(x) (modp);
звідки
f(x)≡(x-α1)(x-α2)f2(x) (mod p).
Аналогічно міркуючи, кінець кінцем прийдемо до тотожної конгруенції (3). З самого процесу одержання многочленів f1(x), f2(x),… fk (x) видно, що старші коефіцієнти цих многочленів однакові і дорівнюють старшому коефіцієнтові a0 многочлена f(x).
В и с н о в о к. Якщо конгруенція (1) п-го степеня за простим модулем р (п можна вважати не більшим за р — 1) має п різних розв'язків α1, α2, . . , αn, то має місце тотожна конгруенція:
f(x) ≡ а0 (х — α1) (х — α2) ... (х — αn) (modp). (4)
Справді, тут k= п, отже, степінь многочлена fn(x) дорівнюватиме п-n=0, тобто fn(х) = а0.
2.2.1.Maкcимaльнe число розв'язків
Теорема 5. Конгруенція п-го степеня за простим модулем не може мати більш як п різних розв'язків.
Справді, нехай β – який-небудь інший розв'язок, відмінний від α1, α2, . . , αn, тобто
β≠αi (modp) (i = 1, 2, … , n);
покладаючи тепер в тотожній конгруенції (4) х=β, знайдемо, що
a0(β – α1)(β – α2) … (β - αn) ≡ 0 (mod p), (4′)
але різниці β — αi за умовою не діляться на р, тобто взаємно прості з р, а в такому разі і їх добуток буде взаємно простим з р. Звідси випливає, що має місце конгруенція (4'), тобто f(β) ≡ 0 (modp), тому а0 має ділитись на р, що суперечить умові, бо в нас a0 ≠ 0 (modp).