Реферат: Сравнения высших степеней

f(х)= а₀ х^п + а₁ х^п-1 + . . . + а_n-1 x + a_n ≡ 0 (mod p), n≥1, (1)

де a₀ ≠0 (modp) і р — просте число.

Теорема 1. Конгруенцію (1) завжди можна так перетворити що її старший коефіцієнт дорівнюватиме одиниці.

Справді, через те що р — просте і a₀ не ділиться на р, то завжди існує єдине число α, що а₀ α ≡ 1 (modp). Помноживши тепер конгруенцію (1) на α і замінивши а₀ x одиницею, дістанемо еквівалентну конгруенцію з старшим коефіцієнтом, що дорівнює одиниці:

xⁿ + b₁ x^{n -1} + .. + b_{n -1} x + b_n ≡ 0 (modp); (1')

тут b_i ≡ a_i α (modp).

Теорема 2. Якщо степінь конгруенції (1) не менший від модуля конгруенції, то вона еквівалентна деякій конгруенції степеня, не вище за р—1 (за тим самим модулем).

Справді, поділимо f(х) на х^р -х; і частку від ділення позначимо через q(x), а остачу через r(х). Тоді на підставі алгоритму ділення з остачею дістанемо:

f(x) = (x^p —x)q(x) + r(x),

де частка q(х) і остача r(х) будуть многочленами з цілими коефіцієнтами, причому степінь r(х) буде не вище р—1. За теоремою Ферма x^p —-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) ділиться на x^p —-x , тобто r(х) ≡ 0 (mod р) – тотожна конгруенція за модулем p, тобто остача при діленні конгруентна з нулем і дана конгруенція еквівалентна конгруенції 0 ≡ 0 (modp) та справедлива при будь-якому цілому x. Далі, нехай остача від ділення f(х) на x^p —-x є многочлен нульового степеня, що дорівнює b_{p -1} . Якщо b_{p -1} не ділиться на p, то дана конгруенція не має розв’язків, бо вона зводиться до невірної конгруенції :

b_{p -1} ≡ 0 (modp).

Приклад. Якій конгруенції нижче від 5-го степеня еквівалентна конгруенція:

f(х) = х¹⁷ + 2x¹¹ + Зx⁸ — 4x⁷ + 2x — 3 ≡ 0 (mod5).

Поділивши f (х) на х⁵ — х і замінивши всі коефіцієнти остачі найменшими невід'ємними лишками за модулем 5, дістанемо, що дана конгруенція еквівалентна конгруенції

r(х) = Зx⁴ + Зx³ + Зx + 2 ≡ 0 (mod 5).

Зауваження. Можна вказане ділення на х^p — х фактично і не виконувати, а просто замінити хⁿ на х^r , де r > 0 є остача від ділення п на р — 1. Справді, за теоремою Ферма х^р ≡ х (mod р), звідси x^{p +1} ≡ x² , x^{p +2} ≡ x³ , ... і взагалі:

Через те що в нашому прикладі x¹⁷ можна замінити через х, а 2x¹¹ через 2x³ , Зx⁸ через Зx⁴ ,—4x⁷ замінити через —4x³ ≡ x³ , тому відразу дістанемо:

f(x) ≡ Зx⁴ + Зx³ + Зx + 2 ≡ 0 (mod 5).

У свою чергу, останню конгруенцію можна спростити так: х ≠ 0 (mod5), тому x^5-1 ≡ 1 (mod5) і

f(x) ≡ Зх³ + Зх ≡ 0 (mod 5),

або

f(x) ≡ х² + 1 ≡ 0 (mod 5).

Очевидні розв'язки останньої конгруенції x ≡ 2, 3 (mod 5) будуть також і розв'язками даної конгруенції:

f(x) ≡ 0 (mod 5).