Сравнения высших степеней - (реферат)
p>Візьмемо деяке натуральне число т; при діленні на т, будь-яких цілих чисел можна дістати тільки т різних невід'ємних остач, а саме: 0, 1, 2, .... , т-1. Отже, множина всіх цілих чисел розіб'ється на т класів чисел, що не перетинаються; при цьому числа, які при діленні на т, даватимуть одну і ту саму остачу r (0 ? r < т), тобто числа, конгруентні за модулем т, утворюють клас чисел за модулем т. Із сказаного випливає, що всім числам даного класу відповідає одна і та сама остачаr; отже, дістанемо всі числа цього класу, якщо в формі mq+r, де r — стале, припустимо, що q набирає значення всіх цілих чисел. З означення конгруентності двох чисел а і b за модулем т із щойно сказаного відразу ж випливає таке твердження. Два цілих числа а і b тоді і тільки тоді належать до одного класу за модулем т, коли вони конгруентні за цим модулем...Позначимо через C0 клас чисел, які діляться на т; через C1— клас чисел, які при діленні на т дають в остачі 1, і т. д. і нарешті, через Cm-1 — клас чисел, які при діленні на т дають в остачі т-1. Будь-яке число даного класу називається лишком, або представником цього класу. Отже, якщо число a є представником деякого класу за модулем т, то будь-яке інше число b цього класу задовольняє умову: b? a(mod m), або b=а + тt, де t — деяке ціле число, тобто, інакше кажучи, b = а + тt є загальний вигляд цілих чисел, які належать до того самого класу, що й а. 2. КОНГРУЕНЦІЇ З НЕВІДОМОЮ ВЕЛИЧИНОЮ
Як видно з наведеного нижче малюнку, конгруенції в теорії чисел поділяються на конгруенції за простим та за складеним модулями.
Види конгруенцій
Рисунок
2. 1. Класи розв'язків конгруенції довільного степеня
Припустимо, що т — натуральне число. Конгруенція виду
f (x) ? 0(mod m), (1) де f (х)= а0хп + а1хп-1 + ... . + аn-1x + an, є многочлен степеня n з цілими коефіцієнтами і а0 ? 0 (mod m) називається алгебраїчною конгруенцією п-го степеня з одним невідомим x. Цілі значення х, що задовольняють конгруенцію (1), називаються коренями або розв'язками цієї конгруенції. Розв'язати конгруенцію — це означає знайти всі значення невідомих, які її задовольняють. Дві конгруенції з одним невідомим називаються еквівалентними, якщо всякий розв'язок однієї конгруенції є розв’язком іншої. Теорема 1. Якщо x = x1 задовольняє конгруенцію (1), то всяке число, яке належить до того самого класу лишків за модулем т , що й число x1, також задовольняє цю конгруенцію, тобто розв'язком буде весь клас чисел х ? х1(mod т).
Це твердження безпосередньо випливає з властивостей конгруенцій. Справді, нехайх2 — будь-яке число, яке належить до того самого класу лишків за модулем т, що й х1; тоді х2 ? x1(mod m). За умовою х1 є розв'язок конгруенції (1), тобто має місце тотожна конгруенція f(x1) ? 0 (mod т), але тоді матиме місце й конгруенція f(x1) ? 0 (mod т), тобто x2 також буде розв'язком конгруенції. Оскільки x2 — будь-яке число класу х ? х1(mod т), то весь цей клас задовольнятиме дану конгруенцію. Розв'язки конгруенції (1), що належать до одного класу чисел за модулем т, приймають за один розв'язок даної конгруенції. При цьому конгруенція (1) має стільки розв'язків, скільки класів чисел її задовольняють.
Приклад. Конгруенція
8x5 — 12x3 — 13x2 — 15x + 6 ? 0 (mod 5)
є еквівалентною конгруенції
Зх5 — 2x3 — Зx2 +1 ? 0 (mod 5),
або конгруенції
Зх5 + 3x3 + 2x2 +1 ? 0 (mod 5).
Щоб знайти розв'язки останньої конгруенції, випробуємо, приклад, абсолютно найменші лишки за модулем 5: 0, 1, 2, -2, -1. Безпосередньо видно, що 0, 1, -1 задану конгруенцію не задовольняють. При дальшому випробуванні можна скористатись схемою Горнера ( Див. Додаток) з тією тільки відмінністю, що для полегшення кожного разу можна відкидати числа, кратні модулю.
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 (mod 5),
як ми вище бачили, має один розв'язок: x ? 1 (mod 5). Але, якщо обидві частини цієї конгруенції помножити на 5, то дістанемо конгруенцію:
5x4 + 5х3 + 5х2 + 5х + 5 ? 0 (mod 5),
розв'язком якої буде вже будь-яке ціле число. Вона, по суті, перетворюється в конгруенцію 0? 0 (mod 5).
Конгруенції виду 0 ? 0 (mod 5) мають очевидно розв'язком будь-яке ціле значення невідомого х, тобто є тотожною конгруенцією. Після наведеного щойно прикладу виникає питання, коли множення обох частин конгруенції з невідомою величиною на ціле число є законним? Відповідь на це дає теорема 2.
Теорема 2. Якщо обидві частини конгруенції (1)помножити на ціле число k, взаємно просте з модулем т, то дістанемо конгруенцію, еквівалентну даній.
Справді, припустимо, що
х = б (mod т)
є який-небудь розв'язок конгруенції (1), тоді
f (б) ? 0 (mod m).
Помножаючи обидві частини цієї конгруенції на k, дістанемо: k•f (б) ? 0 (mod m). (2) Отже, ми бачимо, що б є розв'язком конгруенції
k•f (x) ? 0 (mod m). (3) Навпаки, якщо б — розв'язок конгруенції (3), тобто k•f (б) ? 0 (mod m), тоді обидві частини конгруенції (2) можна скоротити на k, не змінюючи модуля, бо (k, m) = 1, (див. властивість 4, п. 1. 1), отже, f (б) ? 0 (mod m),
тобто б є розв'язком конгруенції (1), що і доводить наше твердження. Зауважимо, що при розв'язуванні конгруенцій з невідомою величиною можна, не змінюючи модуля, скорочувати обидві частини конгруенції тільки на такий їх спільний дільник, який є взаємно простий з модулем (див. властивість 4, п. 1. 1).
2. 2. Конгруенції n-го степеня за простим модулем.
У попередньому параграфі ми бачили, що дослідження й розв'язання конгруенції п-го степеня (п? 1) зводиться кінець кінцем до дослідження і розв'язання відповідних конгруенцій за простими модулями. Тому зараз доведемо деякі загальні теореми, що стосуються конгруенційn-го степеня за простим модулем р.
Припустимо, що задано конгруенцію [1 Рівняння
a0xn+a1xn-1+…+an-1x+an=pt(*)
з цілими коефіцієнтами і p>1 еквівалентне конгруенції (1). Внаслідок такої залежності задачу на розв’язання рівняння (*) в цілих числах можна замінити задачею про розв’язання конгруенції (1), що і застосовується в теорії чисел. ]: f (х)= а0хп + а1хп-1 + ... . + аn-1x + an ? 0 (mod p), n? 1, (1) де a0? 0 (mod p) і р — просте число.
Теорема 1. Конгруенцію (1) завжди можна так перетворити що її старший коефіцієнт дорівнюватиме одиниці.
Справді, через те що р — просте і a0 не ділиться на р, то завжди існує єдине число б, що а0б ? 1 (mod p). Помноживши тепер конгруенцію (1) на б і замінивши а0x одиницею, дістанемо еквівалентну конгруенцію з старшим коефіцієнтом, що дорівнює одиниці:
xn + b1xn-1+ ... + bn-1x + bn ? 0 (mod p); (1') тут bi ? aiб (mod p).
Теорема 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).
