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

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

Доведення. 1) .

2) Для всіх бо хоч одне натуральне число, менше за і взаємно просте з , - одиниця, завжди існує.

3) Нехай і натуральні числа, причому . Підрахуємо кількість натуральних чисел, менших за і взаємно простих з . Для цього розмістимо у вигляді таблиці всі числа від 1 до :

Взаємно простими з , очевидно, будуть ті і тільки ті числа, які взаємно прості і з , і з . Тому відберемо спочатку ті числа, які взаємно прості з , а потім з них відберемо ті, які ще взаємно прості з числом . З числом взаємно простих чисел у першому рядку є чисел. Вони утворюють ЗСЛ за модулем і є представниками класів чисел, в яких всі числа взаємно прості з . Нехай в (11) число задовольняє умову Тоді всі числа класу будуть взаємно прості з . У стовпчику таблиці (11), який починається числом , міститься чисел класу . Отже, у таблиці (11) існує стовпчиків, кожний з яких містить чисел, взаємно простих з . Усього таких чисел .

Розглянемо тепер усі n елементів будь-якого r-го стовпчика таблиці (11):

(12)

Числа послідовності (12) утворюють ПСЛ за модулем . Крім того, числа (12) є значеннями лінійної форми , де пробігає ПСЛ за модулем : 0,1,2,...,, причому . Але тоді за теоремою 5 і лінійна форма пробігає ПСЛ за модулем . Отже, числа го стовпчика утворюють ПСЛ за модулем , серед яких є чисел, взаємно простих з .

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

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

(13)

Доведення. Перш за все зазначимо, що для простого числа p

, (14)

що безпосередньо випливає з означення функції Ейлера.

Випишемо тепер всі натуральні числа від 1 до :

(15)

Числа (15) можна поділити на групи по послідовних натуральних чисел:

.

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

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

,

то

. (16)

Доведення. Оскільки мультиплікативна функція, а - прості числа, то на основі (13) маємо

і тому

.

Теорему доведено.

Приклад. Для = 45 =

.

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

. (17)

[Доведення самостійно. Алгебра і теорія чисел, ч.2. Завало С. Т.,Костарчук В. М., Хацет Б. І. “Вища школа”, 1976, стор. 173-174]

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

. (18)

Доведення. Нехай числа

(19)

утворюють ЗСЛ найменших невід’ємних лишків за модулем . Тоді при числа утворюють теж ЗСЛ за модулем . Ці числа належать якимсь класам, взаємно простим з модулем . Числа можна замінити системою найменших невід’ємних лишків

(20)

з тих же класів, до яких вони належать. Вважаючи, що

перемножимо ці конгруенцій. Дістанемо

.

Оскільки (19) і (20) – це ті самі числа, взаємно прості з m, то, скорочуючи на них обидві частини конгруенції за властивістю _ дістанемо

,

що й треба було довести.

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

. (21)

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

(22)

Приклад. Знайти остачу від ділення на 17. Оскільки 17 – просте число і , то за (21) . Підносячи до квадрата обидві частини конгруенції, далі маємо . Крім того, . Далі дістаємо

.

Отже, остача дорівнює 14.

Контрольні запитання:

1. Які числа називаються конгруентними? Якій рівності еквівалентна конгруенція?

2. Що означає запис ?

3. Яка необхідна і достатня умова конгруентності двох чисел за модулем ?

4. Встановити конгруентність чисел 726 і 162 за модулем 5, користуючись: а) означенням; б) ознакою конгруентності чисел за модулем.

5. Сформулювати властивості конгруенцій, аналогічні властивостям рівностей.

6. Сформулювати властивості конгруенцій, відмінні від властивостей рівностей.

7. Сформулювати правило скорочення конгруенцій.

8. Записати по кілька чисел, що належать до кожного класу за модулем 6.

9. Яка умова є необхідною і достатньою для того, щоб числа належали до того самого класу за модулем ?

10. За яких умов числа і належать до одного і того ж класу лишків за модулем ?

11. Яке означення операцій „додавання” і „множення” класів?

12. Що розуміють під словами: множина містить дільники нуля?

13. Наведіть приклад кільця класів чисел з дільниками нуля.

14. Як дістати повну систему лишків за модулем ?

15.Напишіть повну систему абсолютно найменших, найменших невід‘ємних лишків і довільних лишків за модулем 9.

16. До яких класів лишків за модулем 8 належать усі прості числа ? Записати загальний вигляд у вигляді рівності і у вигляді конгруенції.

17. Сформулюйте основні властивості повної системи лишків.

18. З якою метою при доведенні теореми 5 використовується умова ?

19. Перевірте справедливість теореми 5 на прикладі.

20. Нехай пробігає повну систему найменших невід‘ємних лишків за модулем 8; знайти відповідні найменші невід‘ємні лишки для виразу .

21.Що називається зведеною системою лишків за модулем 7

22. Сформулюйте основні властивості зведеної системи лишків.

23. Якими елементами відрізняється зведена система лишків за простим модулем від повної системи лишків за цим модулем?

24. Запишіть зведену систему найменших невід‘ємних лишків і довільну зведену систему лишків за модулем 14.

25. Скільком класам лишків за модулем 21 належать лишки із одного класу за модулем 7?

26. Чи пробігає вираз , де , зведену систему лишків за модулем при умові, що пробігає зведену систему лишків?

27. Перевірте справедливість теореми 6 на числовому прикладі.

28. Як зрозуміти, що для кожного класу чисел, взаємно простих з модулем, існує обернений клас?

29. Нехай ; знайти: а) ; б) ; в) клас, протилежний до класу ; г) класи, які є дільниками нуля.

30. Які з класів лишків за модулем 15 є оборотними? Якщо такі класи існують, знайти їм обернені.

31. Чи може бути добуток двох необоротних класів лишків стати оборотним? добуток оборотного класу лишків на необоротний клас лишків.

32. Чи утворює сукупність усіх класів чисел за модулем групу відносно множення класів? Те саме відносно додавання класів?

33. Сформулюйте теореми Ейлера і Ферма.

34. Які властивості має функція Ейлера?

35. Запишіть тотожність Гаусса. В чому полягає тотожність Гаусса?

36. З якою метою використовується при доведенні теореми Ейлера умова ?

37. Сформулюйте теорему Ейлера і Ферма для числових конгруенцій.

38. Перевірте справедливість теореми Ейлера на числовому прикладі .

39. Покажіть, що . (При розв‘язуванні розгляньте два випадки: і ).

21