Системи конгруенцій першого степеня
Розглянемо систему конгруенцій першого степеня, але з різними модулями:
. (31)
Розв'язати систему конгруенцій з одним невідомим – означає знайти такі цілі значення невідомого х, які задовольняли б усі конгруенції цієї системи
Дві системи конгруенцій з невідомим х називають рівнозначними (або еквівалентними ), якщо їх задовольняють ті самі значення невідомого х. Якщо за деяким модулем задовольняють систему (31), то весь цей клас чисел вважатимемо за один розв'язок цієї системи. Якщо ця система має хоча б один розв'язок, то вона називається сумісною.
Зауважимо, що, розв'язуючи окремо кожну з конгруенцій (31), матимемо систему, еквівалентну заданій:
(32)
Отже, досить уміти розв'язувати систему конгруенцій (32).
Неважко показати, що коли система (32) сумісна, то вона має єдиний розв'язок за модулем , що дорівнює найменшому спільному кратному чисел .
Теорема 16. Якщо модулі попарно взаємно прості, то система конгруенцій (32) має єдиний розв'язок:
, (33)
де
,
Причому числа і визначаються з умов:
(34)
[Доведення див. Бородін О. І. Теорія чисел. «Вища школа», 1970, 275 стор.]
У загальному випадку, коли модулі можуть і не бути попарно взаємно простими, систему (32) можна розв'язати так.
З першої конгруенції системи (32) випливає, що всі значення х які його задовольняють, матимуть форму , де пробігає всі цілі числа. Щоб вибрати з них значення х , які б задовольняли й другу конгруенцію, визначимо з умови, що
або
Ця конгруенція першого степеня щодо матиме розв'язки, якщо ділиться на ; інакше ця остання конгруенція не має розв'язків, а значить система (32) несумісна. Нехай ділиться на . Розв'язуючи цю конгруенцію, дістанемо:
Тоді сукупність усіх значень , що задовольняють другу конгруенцію, буде:
де пробігає всі цілі числа. Звідси дістанемо:
(35)
де задовольнятимуть перші дві конгруенції. Тепер з чисел (35), аналогічно, виберемо ті, які задовольнятимуть третю конгруенцію. Так знову, або прийдемо до конгруенції відносно , яка не має розв'язків, а значить система (32) несумісна, або знайдемо, що значення
де ціле, або
Задовольнятимуть перші три конгруенції і т.д. Якщо така система (32) сумісна, то, зрештою прийдемо до єдиного розв'язку цієї системи за модулем
Зауваження. Якщо в системі (31) для деяких і ділиться на , тоді -та конгруенція системи (31) матиме розв'язків, і ми дістанемо кілька систем конгруенцій виду (32); тому система (31) матиме декілька розв'язків. Для складання систем виду (320 треба кожен розв'язок однієї конгруенції системи (31) скомбінувати з кожним розв'язком решти конгруенцій цієї системи.
Невизначене рівняння першого степеня
Означення 13. Діофантовим рівнянням 1-го степеня з n невідомими називається рівняння виду
(36)
де всі коефіцієнти і невідомі – цілі числа і хоча б одне .
Означення 14. Розв'язком діофантового рівняння (36) називається сукупність цілих чисел , яка задовольняє цьому рівнянню.
Теорема 17. Якщо коефіцієнти діофантового рівняння
взаємно прості числа, то воно має розв'язки на множині цілих чисел.
Теорема 18. Нехай - найбільший спільний дільник коефіцієнтів . Діофантове рівняння (36) має розв'язок тоді і тільки тоді, коли . Число розв'язків такого рівняння або дорівнює нулю, або нескінченності.
Теорема 19. Якщо є розв'язком конгруенції , то сукупність буде розв'язком діофантового рівняння
.
Теорема 20. Нехай - найбільший спільний дільник і , де , і - один із розв'язків діофантового рівняння:
(37)
Тоді множина розв'язків рівняння (37) в цілих числах співпадає з множиною сукупностей , де
, (38)
а - довільне ціле число.
Конгруенції го степеня за простим модулем
Число розв'язків конгруенції го степеня
Припустимо, що задано конгруенцію:
(а)
де і просте число.
Теорема А. Конгруенцію (а) завжди можна замінити еквівалентною конгруенцією того самого степеня з старшим коефіцієнтом, що дорівнює одиниці.
Справді, так як просте число і , то завжди існує єдине число таке, що (див. теорему 13, лекція 2). Помножимо тепер конгруенцію (а) на і замінимо одиницею, дістанемо еквівалентну конгруенцію з старшим коефіцієнтом, що дорівнює одиниці:
; (б)
тут .
Теорема Б. Якщо степінь конгруенції (а) не менший від модуля конгруенції, то вона еквівалентна деякій конгруенції степеня не вище (за тим самим модулем).
,
і
Розглянемо методику розв'язування конгруенцій го степеня виду
, (39)
де просте число. За допомогою операцій, які приводять до рівносильних конгруенцій, можна побудувати рівносильну до (39) конгруенцію степеня, не вище , з коефіцієнтами, які є найменшими невід'ємними або абсолютно найменшими лишками ПСЛ за модулем p.
Побудову такої конгруенції можна провести в такому порядку.
а) Замінити всі коефіцієнти многочлена відповідними їм найменшими невід'ємними або абсолютно найменшими лишками з ПСЛ за модулем p.
б) Зробити коефіцієнт при старшому члені конгруенції рівним одиниці.
в) Понизити степінь конгруенції.
Якщо степінь , то конгруенцію (39) можна замінити рівносильною їй конгруенцією степеня, не вищого . За наслідком теореми Ферма (Лекція 2) для будь-якого цілого числа і простого
,
або
. (40)
З другого боку, ділячи многочлен на , дістанемо
.
Враховуючи це, на основі конгруенції (40) матимемо
,
тобто
. (41)
На основі теореми Ейлера
.
Тому
,
тобто .
Число розв'язків конгруенції n-го степеня
Теорема 21. Конгруенція го степеня за простим модулем може мати не більш як розв'язків.
Означення 15. Якщо всі коефіцієнти многочлена є кратними модуля , то конгруенція
називається тотожною конгруенцією.
Теорема 22. Якщо конгруенція -го степеня має розв’язків, то всі її коефіцієнти кратні модулю, тобто ця конгруенція тотожна.
Теорема 23. Якщо - який-небудь розв'язок конгруенції (39), то має місце тотожна конгруенція:
, (*)
де - многочлен степеня, на одиницю нижчого від степеня многочлена . Старший коефіцієнт многочлена збігається із старшим коефіцієнтом даного многочлена .
Висновок. Конгруенція (39) має корінь тоді і тільки тоді, коли ліва її частина ділиться на за даним модулем .
Теорема 24. Якщо є різні розв'язки конгруенції (39), то має місце тотожна конгруенція:
, (**)
де степінь дорівнює і старші коефіцієнти і однакові.
Висновок. Якщо конгруенція (39) -го степеня за простим модулем ( можна вважати не більшим за ) має різних розв'язків , то справедлива тотожна конгруенція:
. (***)
Теорема 25 (Вільсона). Якщо - просте число, то
Зведення конгруенції за складеним модулем
до системи конгруенцій за простими модулями
Теорема 26. Якщо - попарно взаємно прості числа, то конгруенція (45) еквівалентна системі конгруенцій:
(46)
При цьому, позначаючи через
Числа розв'язків окремих конгруенцій (46) за відповідними модулями і через - число розв’язків конгруенції (45), матимемо:
.
Висновок 1. Якщо хоч одна з конгруенцій системи (46) не має розв'язків, то й задана конгруенція (45) також не матиме розв'язків.
Висновок 2. Дослідження і розв'язування конгруенції
,
де - канонічний розклад модуля , зводиться до дослідження і розв'язування конгруенцій:. Це випливає з того, що числа попарно взаємно прості.
Отже, все зводиться до того, що доводиться окремо досліджувати і розв'язувати конгруенції виду
, (47)
де - просте число, - ціле додатне число. Зауважимо, що всякий розв'язок конгруенції (47) буде розв'язком конгруенції
. (48)
Очевидно, якщо конгруенція (48) не має розв'язків, то й конгруенція (47) розв'язків не матиме. Справді, якщо не ділиться на , то і поготів не ділитиметься на , тобто
ні при якому цілому .
Теорема 27. Всякий розв'язок
конгруенції (48) при умові, що не ділиться на , дає один єдиний розв'язок конгруенції (47)
. (49)
Зауваження. Якщо ділиться на і не ділиться на , то це означає, що яке б не було
і конгруенція (49), а, значить, конгруенція (47) не має розв'язків для розглядуваного . Якщо ж ділиться на , тобто , то буде вже розв'язком конгруенції .
Означення 16. Якщо конгруенція має розв'язок, то називається лишком степеня за простим модулем , якщо ні, - то нелишком степеня за модулем .
(51)
Теорема 28. Якщо - квадратичний лишок за модулем , , то квадратна конгруенція
(53)
має два розв'язки.
Теорема 29. Для будь-якого простого числа половина лишків ЗСЛ є квадратичними лишками, а половина – квадратичними нелишками.
Терема 30. (Критерій Ейлера). При простому число є квадратичним лишком за модулем тоді і тільки тоді, коли
,
і квадратичним нелишком тоді і тільки тоді, коли
.
Означення 17. Символ Лежандра визначається для всіх цілих чисел , які не діляться на просте число рівністю
Використовуючи критерій Ейлера, очевидно, маємо
(57)
Властивості символу Лежандра
1. Якщо , то .
Якщо , то .
Всі числа є одночасно або квадратичними лишками, або квадратичними нелишками за модулем .
2. .
Із (57) і теореми Ферма
.
3.
Наслідок 2.
4.
Це випливає з (57). Якщо вважати , то
.
Цю властивість можна конкретизувати.
Якщо , то
.
Якщо , то
.
Отже, число є квадратичним лишком за модулем , якщо можна подати у вигляді , і квадратичним нелишком за модулем , якщо має вигляд
5. .
.
Наслідок 1. .
Наслідок 2. .
Наслідок 3. Якщо число не ділиться на просте число і в канонічному розкладі на добуток простих множників має вигляд
,
то
(58)
6. .
За модулем 8 всі непарні числа можна подати у вигляді
,
або
При число є парним, а при є непарним. Звідси випливає твердження: Число 2 є квадратичним лишком за простим модулем , якщо подано у вигляді суми і квадратичним нелишком за модулем , якщо подано у вигляді
7. Закон взаємності квадратичних лишків:
Розв'язування квадратичних конгруенцій
Критерій Ейлера і символ Лежандра дають можливість встановити, чи є число квадратичним лишком за модулем , чи має розв'язки квадратна конгруенція
(59)
При малих цю конгруенцію розв'язують методом проб, при великих необхідно встановити, чи має ця конгруенція розв'язок, тобто чи є квадратичним лишком. Тоді за критерієм Ейлера маємо
.
Якщо число має вигляд , то
.
Помноживши на обидві частини конгруенції, матимемо
,
або
.
Очевидно, дає нам класи чисел і , які є розв'язками конгруенції (59).
Конгруенції 2-го степеня за складеним модулем
Конгруенція другого степеня за складеним модулем:
(60)
досліджується і розв‘язується згідно з вказівками зазначеними в лекції 3 модуля 2.
За теоремою 26, конгруенція (60) еквівалентна системі конгруенцій
(61)
Розглянемо конгруенції виду
(62)
де - ціле число, а - просте непарне число.
Теорема 31. Конгруенція (62) має два розв‘язки або не має жодного залежно від того, чи буде число квадратичним лишком або нелишком за модулем , тобто чи буде відповідно або .
Зауваження. Неважко побачити, що коли є один розв‘язок конгруенції (62), то другим її розв‘язком буде .
Розглянемо конгруенцію
(63)
Теорема 32. 1) Конгруенція (63) завжди має один розв‘язок при 2) два розв‘язки – при і і жодного при і 3) при конгруенція (63) має розв‘язки тільки при і при цьому чотири різних розв‘язки; два з них неодмінно задовольняють і конгруенцію
.
Теорема 33. Конгруенція
(64)
має розв‘язок тоді і тільки тоді, коли
при
при
Якщо жодну з цих умов не порушено, то кількість розв‘язків буде
при
при
при
Зауваження. Якщо - непарне і конгруенція (64) має розв‘язки, то символ Якобі
,
бо всі . Ця умова необхідна для розв‘язності конгруенції (64), але не достатня, бо з не виходить, що всі . У зв‘язку з цим можемо зауважити, що застосування символу Якобі та його властивостей лише прискорює обчислення символу Лежандра.
Розглянемо множину цілих додатних степенів числа :
(65)
з точки зору їх конгруентності за деяким модулем , вважаючи, що . За теоремою Ейлера маємо:
,
і, отже,
.
Таким чином, серед степенів (65) числа знайдеться нескінченна кількість чисел, конгруентних з 1 за модулем .
Означення 18. Найменше натуральне число , для якого справедлива конгруенція , називається показником, до якого належить число , за модулем . . Якщо , число називається первісним коренем за модулем .
Приклад 1. Знайти , якщо .
Теорема 34. Якщо , то числа і належать до того самого показника за цим модулем.
Наслідок. Усі числа одного класу належать тому самому показнику за модулем .
Властивості показників за модулем
1. Якщо і - показник, до якого належить число за модулем , то серед степенів
(66)
немає чисел, конгруентних між собою за модулем .
Наслідок. Якщо - первісний корінь за модулем , тобто , то множина степенів
(67)
є ЗСЛ за модулем .
2. Якщо , то
.
Наслідок 1. Якщо число належить до показника за модулем і , то .
Наслідок 2. Показник , до якого належить число за модулем , є дільником числа .
3. Теорема 35. Якщо число належить до показника за модулем , а число - до показника за модулем і , то добуток чисел належить до добутку показників за модулем .
Наслідок. Якщо числа належать за модулем відповідно до показників , які попарно взаємно прості між собою, то
(68)
тобто показник, до якого належить добуток чисел за модулем , дорівнює добутку показників, до яких належать числа за модулем .
Існування первісних коренів
Теорема 36. За будь-яким простим модулем існує хоча б один первісний корінь.
Число класів первісних коренів
Теорема 37. Якщо існує хоч одне число, яке належить до показника за модулем , то всього класів таких чисел є .
Наслідок 1. Первісних коренів за модулем існує.
Наслідок 2. Якщо - первісний корінь за модулем , то інші первісні корені слід шукати серед степенів - вони мають вигляд , де і .
Теорема 38. Якщо - канонічний розклад числа , то для того щоб число було первісним коренем за модулем , достатньо, щоб виконувались умови:
для всіх .
Індекси за простим модулем
ЗСЛ за модулем можна подати сукупністю чисел – найменших невід‘ємних лишків
. (69)
ЗСЛ можна подати й інакше – за допомгою степенів якогось первісного кореня за модулем . Якщо є первісний корінь за модулем [ ], то степені
(70)
є також сукупністю чисел, неконгруентних між собою за модулем (властивість 1 показників за модулем). Тому ці числа є також представниками різних класів лишків за модулем і утворюють ЗСЛ за модулем . Кожне число з (69) конгруентне деякому числу з (70). Звідси кожний клас лишків ЗСЛ за модулем можна подати якимсь числом виду . Тим самим кожному класу лишків ЗСЛ можна поставити у відповідність показник степеня числа , який і називається індексом класу при основі .
Означення 19. Індексом числа за модулем (або класу ) при основі називається таке ціле невід‘мне число , що
.
Позначають індекс за модулем .
Основні властивості індексів
1.Числа є індексами числа за модулем при основі тоді і тільки тоді, коли
за модулем.
2. Для того щоб
,
необхідно і достатньо, щоб виконувалася конгруенція
.
3. .
4. .
5. Індекс добутку чисел за модулем при основі конгруентний за модулем сумі індексів окремих множників при основі , тобто
.
6. .
7. Якщо , то .
Зауважимо, що перехід від конгруенції між числами до конгруенції їх індексів називається індексацією, а зворотний перехід – потенціюванням.
Розв‘язування двочленних конгруенцій -го степеня
за допомогою індексів
В загальному вигляді двочленні конгруенції можна записати так:
, (71)
де і - натуральне число.
Якщо провести індексацію цієї конгруенції при однаковій основі, то дістанемо конгруенцію , або, що те ж саме,
. (72)
Конгруенції (71) і (72) еквівалентні. Якщо позначити
.
то конгруенція (72) має вигляд
. (73)
Тим самим від конгруенції -го степеня (71) за допомогою індексації ми прийшли до конгруенції (72) першого степеня. Розв‘язавши її і взявши величину , знайдемо за відповідними таблицями.