Системи конгруенцій першого степеня

Теорема 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) першого степеня. Розв‘язавши її і взявши величину , знайдемо за відповідними таблицями.