1. Конгруенції та їх основні властивості

Припустимо, що т є натуральне число; розглядатимемо цілі числа у звязку з остачами від ділення їх на це натуральне яке називають модулем. Згідно з теоремою про ділення з остачею кожному числу а відповідатиме певна остача і від ділення а на т:

, .

Якщо двом цілим числам і відповідає одна й та сама остача від ділення їх на т, то вони називаються конгруентними (або порівнянними) за модулем т. Це позначається символом:

(1)

читається: а конгруентне з за модулем т.

Деякі автори позначають це коротше:

(1)

Співвідношення (1) [або (1)] між числами називають конгруенцією, або порівнянням.

Приклади. ; ; .

Теорема 1. Конгруентність чисел і за модулем рівнозначна:

а) можливості подати а у формі , де - ціле;

б) подільності - на .

Властивості:

1. Для конгруенції справджуються закони: рефлективності, симетричності і транзитивності, тобто відповідно:

a) ;

б) з конгруенції випливає, що ;

в) якщо і , то .

2. Конгруенції за одним і тим самим модулем можна почленно додавати (або віднімати).

Висновок 1. Доданок, що стоїть у якій-небудь частині конгруенції, можна переносити в іншу частину, змінивши знак на протилежний.

Висновок 2. Можна додати до обох частин або відняти від обох частин конгруенції одне й те саме число.

Висновок 3. До кожної частини конгруенції можна додати (або відняти від неї) довільне число, кратне модулю.

3. Конгруенції за одним і тим самим модулем можна почленно перемножати.

Висновок 1. Обидві частини конгруенції можна помножити на одне й те саме ціле число.

Висновок 2. Обидві частини конгруенції можна підносити до одного й того самого цілого невідємного степеня, тобто якщо. , то , де - ціле.

4. Обидві частини конгруенції можна поділити на їхній спільний дільник, якщо він взаємно простий з модулем.

5. Обидві частини конгруенції і модуль можна помножити на одне й те саме натуральне число.

6. Обидві частини конгруенції і модуль можна поділити на будь-який їхній спільний дільник.

7. Якщо конгруенція має місце за кількома модулями, то вона матиме місце і за модулем, що дорівнює їхньому найменшому спільному кратному.

теорія конгруенція ейлер ферм

8. Якщо конгруенція має місце за модулем , то вона матиме місце і за будь-яким дільником цього модуля.

9. Якщо одна частина конгруенції і модуль діляться на яке-небудь ціле число, то і друга частина конгруенції ділиться на це число.

10. Числа і , конгруентні між собою за модулем , мають з ним один і той самий найбільший спільний дільник.

Візьмемо деяке натуральне число , взаємно просте з модулем , розглянемо послідовні степені : . Всі числа цієї нескінченної множини розподілені в класах, отже, принаймні один з цих класів повинен містити нескінченну множину степенів . Узявши з цього класу два степені і позначивши їх і , де , матимемо . Оскільки з слідує , то . Таким чином, для деякого маємо , причому оскільки то . Тоді і при будь-якому натуральному матимемо , що доводить існування нескінченної множини степенів , що належать класу .

П. Ферма для простого модуля, а Л. Ейлеру для будь-якого модуля вдалося вказати значення , при яких має місце рівність . Відповідні теореми, ми їх називатимемо теоремами Ферма - Ейлера, є основою всієї теорії порівнянь і широко використовуються як в теоретичних дослідженнях, так і в арифметичних застосуваннях.

Теорема Ферма. Для будь-якого простого і будь-якого , що не ділиться на , справедливе порівняння

.

Теорема Ейлера. Для будь-якого модуля і будь-якого , взаємно простого з , справедливе порівняння

.