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

В лекції 4 модуля 1 було введене поняття числових функцій, які визначені для всіх натуральних значень аргументу; було розглянуто деякі числові функції.

У теорії чисел використовують ряд спеціальних функцій, які дають важливу арифметичну характеристику цілих чисел. Однією з таких функцій є (читається „ант’є від х ”), яка задана на множині всіх дійсних чисел; [ x ] – це найбільше ціле число, менше за х. За допомогою функції [ x ] можна, наприклад, вказати степінь, з яким у канонічний розклад числа n! входить простий множник p. Цей степінь дорівнюватиме такому натуральному числу:

Означення 9. Числова функція , визначена на множині натуральних чисел, називається мультиплікативною, якщо для кожного n і для будь-яких взаємно простих натуральних чисел n і m

(9)

Мультиплікативні функції мають такі властивості:

1) Якщо - мультиплікативна функція, то

2) Якщо - мультиплікативна функція і числа попарно взаємно прості, то

(10)

3) Добуток мультиплікативних функцій є мультиплікативна функція.

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

Теорема 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. Якщо і число не ділиться на , то конгруенція не має розв‘язків.