Китайська теорема про остачі.

Конгруенції з одним невідомим.

Доведення теореми Эйлера.

Теореми Ейлера і Ферма.

При первісні корені завжди існують.

Число називається первісним коренем (первісним елементом) за модулем , якщо його порядок по модулі дорівнює .

Відомо, що в кожному скінченному полі також існує первісний елемент (генератор поля). Степені первісного елемента представляють усі ненульові елементи поля.

Зокрема, якщо первісний елемент поля , те порівняння розв'язне для ненульових лишків за модулем .

Показник у цьому порівнянні називається дискретним логарифмом числа за основою . Дискретні логарифми часто називають індексами і позначають або .

Теорема Ейлера. Якщо , то .

З теореми Ейлера випливає мала теорема Ферма: , де - простої, .

Ці теореми інтенсивно використовуються в асиметричній криптографії і, крім того, дуже корисні для скорочення обчислень.

Як наслідок, з теореми Ейлера випливає, що елемент є первісним коренем за модулем тоді і тільки тоді, коли виконуються співвідношення: , де .

Зауважимо, що в кожному скінченному полі , при , , виконується співвідношення . Це зв'язано з тим, що число є порядком мультиплікативної групи поля.

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

Нагадаємо, що розширення скінченного поля може бути представлене як кільце лишків многочленів за модулем незвідного многочлена, над простим полем: .

Для деяких незвідних многочленів послідовність пробігає всі можливі лишкі, тобто всі елементи поля. Такі многочлени називаються примітивними.

Нехай - всі різні числа, які взаємно прості з і не перевищують . Очевидно, .

Оскільки, , у послідовності будь-які два члени з різними індексами непорівнянні за модулем .

Тому послідовності і співпадають, з точністю до перестановки членів.

Отже, добуток всіх членів однієї послідовності і добуток всіх членів іншої послідовності порівнянні за модулем , звідки, після скорочення на , одержуємо .

Нехай числа попарно взаємно прості і . Тоді існує єдиний за модулем розв’язок системи порівнянь , .

При цьому, , де , .

Дійсно, у зазначеному вирзі для , один доданок порівнянний з за модулем , а всі інші порівнянні з нулем.

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

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