b> 2.1. Класи розв'язків конгруенції довільного степеня
Пріпустімо, Що т - натуральне число. Конгруенція увазі
f (x) в‰Ў 0 (mod m), (1)
де f (х) = а 0 х п + а 1 х п-1 +. . . + А n-1 x + A n , є многочлен степеня n з цілімі коефіцієнтамі и а 0 в‰ 0 (mod m) назівається алгебраїчною конгруенцією п-го степеня з одним невідомім x.
Цілі значення х, Що задовольняють конгруенцію (1), назіваються корінь або розв'язку цієї конгруенції.
розв'язати конгруенцію - ції означає знайте ВСІ Значення невідоміх, які її задовольняють.
Дві конгруенції з одним невідомім назіваються еквівалентнімі, ЯКЩО всякий розв'язок однієї конгруенції є Розв'язка іншої.
Теорема 1. ЯКЩО x = x 1 задовольняє конгруенцію (1), то всяке число, його призначення та належиться до того самого класу лішків за модулем т, Що й число x 1 , кож задовольняє Цю конгруенцію, тобто розв'язку буде весь клас чисел
х в‰Ў х 1 (mod т).
Це твердження безпосередню віпліває з властівостей конгруенцій. Справді, нехай х 2 - будь-яке число його призначення та належить до того самого класу лішків за модулем т, Що ї х 1 ; тоді х 2 в‰Ў x 1 (mod m). За Умова х 1 є розв'язок конгруенції (1), тобто має Місце тотожня конгруенція f (x 1 ) в‰Ў 0 (mod т), альо тоді матіме Місце ї конгруенція f (x 1 ) в‰Ў 0 (mod т), тобто x 2 кож буде Розв'язка конгруенції. Оскількі x 2 - будь-яке число класу х в‰Ў х 1 (mod т), то весь цею клас задовольнятіме дану конгруенцію.
розв'язку конгруенції (1), Що належать до одного класу чисел за модулем т, пріймають за один розв'язок даної конгруенції. При цьому конгруенція (1) має стількі розв'язків, скількі класів чисел її задовольняють.
Приклад. Конгруенція
8x 5 - 12x 3 - 13x 2 - 15x + 6 в‰Ў 0 (mod 5)
є еквівалентною конгруенції
Зх 5 - 2x 3 - Зx 2 +1 в‰Ў 0 (mod 5),
або конгруенції
Зх 5 + 3x 3 + 2x 2 +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 + 3x 3 + 2x 2 +1 в‰Ў 0 (mod 5) не має розв'язків, а тому не має розв'язків и конгруенція
8x 5 - 12x 3 - 13x 2 - 15x + 6 в‰Ў 0 (mod 5).
При розв'язуванні конгруенції з невідомою величиною іноді доводитися множіті обідві Частина конгруенції на ціле число. Для тотожня конгруенцій ця Операція, Як раніш Було показано, Завжди законна. Для конгруенцій з невідомою величиною таке перетворення НЕ Завжди Закон, тобто, інакше Кажучи, при такому перетворенні конгруенції Може порушітісь еквівалентність даної и добутої конгруенцій.
Приклад. Конгруенція
x 4 + х 3 + Х 2 + х + 1 в‰Ў 0 (mod 5),
Як ми Вище Бачили, має один розв'язок: x в‰Ў 1 (mod 5). Альо, ЯКЩО обідві Частина цієї конгруенції помножіті на 5, то дістанемо конгруенцію:
5x 4 + 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]:
f (х) = а 0 х п + а 1 х п-1 +. . . + А n-1 x + a n в‰Ў 0 (mod p), n ≥ 1, (1)
де a 0 в‰ 0 (Mod p) i р - Прості числа.
Теорема 1. Конгруенцію (1) Завжди можна так перетворіті Що її старший коефіцієнт дорівнюватіме одініці.
Справді, через ті Що р - просте и a 0 не діліться на р, то Завжди існує єдине число О±, Що а 0 О± в‰Ў 1 (mod p). Помноживши тепер конгруенцію (1) на О± и замінівші а 0 x одиницею, дістанемо еквівалентну конгруенцію з старшим коефіцієнтом, Що дорівнює одініці:
x n + b 1 x n -1 + .. + B n -1 x + b n в‰Ў 0 (mod p); (1 ')
тут b i в‰Ў a i О± (Mod p).
Теорема 2. ЯКЩО степінь конгруенції (1) не менший від модуля конгруенції, то вон еквівалентна деякій конгруенції степеня, не Вище за р-1 (за тім самим модулем).
Справді, поділімо f (х) на х р -х: i частко від ділення позначімо через q (x), а остачу через r (х). Тоді на підставі алгоритму ділення з остачею дістанемо:
f (x) = (X p -x) q (x) + r (x),
де Частка q (х) i остача r (х) Будуть многочленами з цілімі коефіцієнтамі, причому степінь r (х) буде не Вище р-1. За теоремою Ферма x p - x в‰Ў 0 (mod p) при будь-якому цілому х, тому дістанемо тотожня конгруенцію:
f (х) в‰Ў r (x) (mod р).
Ця тотожня конгруенція показує, Що корені конгруенції (1) i конгруенції r (х) в‰Ў 0 (mod р) однакові. Оскількі х р - х Завжди діліться на p, то f (...
