Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата

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

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

f(x) = (xp—x)q(x) + r(x),

де частка q(х) і остача r(х) будуть многочленами з цілими коефіцієнтами, причому степінь r(х) буде не вище р—1. За теоремою Ферма xp—-x ≡ 0 (mod p) при будь-якому цілому х, тому дістанемо тотожну конгруенцію:

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 (mod p) та справедлива при будь-якому цілому x. Далі, нехай остача від ділення f(х) на xp—-x є многочлен нульового степеня, що дорівнює bp-1. Якщо bp-1 не ділиться на p, то дана конгруенція не має розв’язків, бо вона зводиться до невірної конгруенції :

bp-1 ≡ 0 (mod p).

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

f(х) = х17 + 2x11 + Зx8 — 4x7 + 2x — 3 ≡ 0 (mod 5).

Поділивши 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 (mod 5), тому x5-1 ≡ 1 (mod 5) і

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)

Рекомендуем скачать другие рефераты по теме: шпаргалки по гражданскому, організація реферат.



Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата

Поделитесь этой записью или добавьте в закладки