Властивості функції Ейлера

Теорема 7. Функція Ейлера мультиплікативна.

Теорема 8. Якщо p – просте число, а k – натуральне число, то

(13)

Теорема 9. Якщо канонічний розклад числа m має вигляд

,

то

. (16)

Теорема 10. Сума значень функції Ейлера для всіх дільників числа m дорівнює m:

. (17)

Теорема 11.(Ейлера ) Якщо m – натуральне число і то

. (18)

Теорема 12 (Ферма). Якщо число р просте і , то

. (21)

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

(22)

Способи розв'язування конгруенцій першого степеня

Означення 10. Конгруенціями з одним невідомим за модулем m називаються конгруенції виду

, (23)

де в лівій частині міститься многочлен з цілими коефіцієнтами.

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

Означення 11. Розв’язком конгруенції називається клас лишків за модулем m, кожне число якого задовольняє цю конгруенцію.

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

Щоб знайти розв’язки, досить підставити в конгруенцію замість невідомого х числа з різних класів за модулем m. Для цього можна перебрати ПСЛ з найменших невід’ємних лишків, а ще краще – повну систему абсолютно найменших лишків.

Означення 12. Конгруенції називаються рівносильними, якщо множини їх розв‘язків збігаються.

Щоб побудувати рівносильні конгруенції, над заданою конгруенцією проводять операції, які ґрунтуються на властивостях конгруенцій, розглянутих раніше. До операцій, які не порушують множину розв‘язків конгруенцій, належать такі:

а) Додавання до обох частин конгруенції будь-якого многочлені з цілими коефіцієнтами.

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

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

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

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

. (25)

При розв‘язуванні таких конгруенцій розглядають два випадки: і .

Теорема 13. Якщо , то конгруенція (25) має єдиний розв‘язок.

Теорема 14. Якщо і , то конгруенція (25) має розв‘язків.

Теорема 15. Якщо і число не ділиться на , то конгруенція не має розв‘язків.