Теорема (Ейлер). Нехай m>1, (a,m)=1, j(m) – функція Ейлера. Тоді:
aj(m) º 1(mod m).
Доказ. Нехай х набуває значення із зведеної системи лишків за mod m:
x=r1,r2,...,rc
де c=j(m) їх кількість, r1,r2,..., rc - найменші невід’ємні лишки за mod m. Отже, найменші невід’ємні лишки, що відповідають числам ax є відповідно:
r 1 , r 2 ,..., r c
– теж набувають значень із зведеної системи лишків, але в іншому порядку (див. Лему 2 з пункту 17). Значить:
a × r1 ºrj1 (mod m)
a × r2 ºrj2 (mod m)
...
a × rc ºrjc (mod m)
Перемножимо ці с порівнянь. Вийде:
ac r1 r2 ...rc ºrj 1 rj 2 ... rj c (mod m)
Оскільки r1 r2 ...rc = r1 r2 ... rc ¹ 0 і взаємно просте з модулем m, то, поділивши останнє порівняння на r1 r2 ...rc, одержимо aj(m) º 1(mod m).
Друга теорема цього пункту - теорема Ферма – є безпосереднім наслідком теореми Ейлера.
Приклад 1. Дев'ятий ступінь однозначного числа закінчується на 7. Знайти це число.
Розв’язування. a9 º 7(mod 10) – дано. Крім того, (7, 10)=1 і ( a , 10)=1. За теоремою Ейлера, aj(10) º 1(mod 10). Отже, a4 º 1(mod 10) і, після піднесення до квадрату, a8 º1(mod 10). Поділимо почленно a9 º 7(mod 10) на a8 º 1(mod 10) і одержимо aº7(mod 10). Це означає, що a=7.
Приклад 4. Знайти дві останні цифри числа 243402.
Рішення. Дві останні цифри цього числа є залишком ділення його на 100. Маємо: 243=200+43; 200+43 º 43(mod 100) і, піднімаючи останнє очевидне порівняння в 402-у степінь, розкриємо його ліву частину за біномом Ньютона. У цьому гігантському виразі всі доданки, крім останнього, містять ступінь числа 200, тобто діляться на 100, тому їх можна викинути з порівняння, після чого зрозуміло, чому 243402 º 43402(mod 100). Далі, 43 і 100 взаємно прості тому, за теоремою Ейлера, 43j(100)º1(mod 100). Вважаємо:
j(100)= j(22 × 52 )=(10–5)(10–2)=40.
Маємо порівняння: 4340º1(mod 100), що піднесемо в десяту степінь і помножимо почленно на порівняння: 432 º 49(mod 100). Одержимо:
отже, дві останні цифри числа 243402 є 4 і 9.
