Використання теореми Ейлера

Знаходження декількох останніх цифр в десятковому запису степенів вигляду mⁿ.

Як знайти три останні цифри в десятковому запису степені 89⁹⁸⁷?

Розв′язання. Знайти помилку:

(80+9) ⁹⁸⁷=(80+9) ^3*7*47=

=(2³*10+9) ^3*7*47=((9⁷)⁴⁷)³= (10у+9)³=

=1000*х +9³=1000*х +729

Зверніть увагу на правильні вирази:

19³=6*1000+859,  а

9⁹⁸⁷= 1000*х+769

89⁹⁸⁷=1000*у+729

109⁹⁸⁷=1000*у+469

Висновок: Не можна користуватися методом (10*у+х)^m для знахлдження останніх трьох цифр. Тут варто користуватися: (1000*у+х)^m  і досліджувати останні цифри числа: х^m

Наприклад, 10009⁹⁸⁷=(1000*у+9)⁹⁸⁷   і досліджувати останні цифри числа: 9⁹⁸⁷. Отже, 1000*х+769.

Використаємо для цього властивості функції Ейлера j(m).

Нагадаємо, функція Ейлера для натурального аргументу m приймає натуральне значення, що означає кількість натуральних чисел, що менші числа m і взаємно прості з числом m.

Наприклад. А)Функція Ейлера для натурального аргументу 10: j(10)=4, бо всього існує чотири числа: {1;3;7;9}, для яких НСД(1;10)= НСД(3;10)= НСД(7;10)= НСД(9;10)=1.

Б)Функція Ейлера для натурального аргументу 10: j(100)=40, бо всього існує 40 чисел: {1;3;7;9, …,99}, для яких НСД(1;100)= НСД(3;100)= НСД(7;100)= …=НСД(99;100)=1.

В)Функція Ейлера для натурального аргументу 10: j(1000)=400, бо всього існує 400 чисел: {1;3;7;9, …,999}, для яких НСД(1;1000)= НСД(3;1000)= НСД(7;1000)= …=НСД(999;1000)=1. Як швидко обчислювати значення функції Ейлера? Це  можна зробити за формулою:

j(m)= m(1-¹/р₁) (1-¹/р₂)…( 1-¹/р_k),

де {р_і , і=1..k}_,– це усі прості числа, які є дільниками числа m.

Наприклад, а)j(10)= 10(1-¹/2) (1- ¹/5)= =10*0,5*0,8 = 4.

б)j(100)= 100(1-¹/2) (1-¹/5)=100*0,5*0,8 =40.

в)j(1000)= 1000(1-¹/2) (1-¹/5)=1000*0,5*0,8= =400.

г)j(10000)= 10000*(1-¹/2)*(1-¹/5) = =10000*0,5*0,8 =4000.

Д) j(10ⁿ)= 10ⁿ(1-¹/2) (1-¹/5)= 10ⁿ *0,5*0,8 =4*10^n-1.

Нам треба для обчислення, що твердження теореми Ейлера: Якщо  m>1,  НСД(a, m) =1 справедлива конгруенція a^j(m) º1(mod m),  де j(m) – функція Ейлера.

Наприклад. А) Не виконуючи великих і складних обчислень, можна знайти чотири останні цифри неймовірно великого числа 3^4000. Для цього варто скористатися теоремою Ейлера: 3^j(10000) º1(mod 10000),  бо НСД(3, 10000) =1, тому 3⁴⁰⁰⁰ º1(mod 10000).  Тому чотири останні цифри числа це 0001, тобто 3⁴⁰⁰⁰=х*10000+1.

Б) Не виконуючи великих і складних обчислень, можна знайти дві останні цифри великого числа 17⁴⁰. Для цього варто скористатися теоремою Ейлера:

j(100)= 100(1-¹/2)(1-¹/5)=100*0,5*0,8  =40.

НСД(17, 100)=1

17⁴⁰º17^j(100) º1(mod 100).  Тому дві останні цифри числа це 01, тобто 17⁴⁰=х*100+1.

Як знайти три останні цифри в десятковому запису степені 89¹²⁰³ºх(mod 1000)?

Для цього варто скористатися теоремою Ейлера:

j(1000)= 1000(1-¹/2)(1-¹/5)=1000*0,5*0,8=400.

НСД(89, 1000)=1

89¹²⁰³º89^{400+400+400+3}º89^j(1000) 89^j(1000) 89^j(1000) 89³  º1*1*89³º89³º704969º969(mod 1000). 

Тому три останні цифри числа це 969.

 тобто

89¹⁸⁷

j(1000)= j(2³5³)= j(2³)j(5³)=2³(1-¹/2)*5³(1-¹/5)=4*100=400

j(5³)= j(125)= 5³(1-¹/5)=100, НСД(89, 125)=1

89¹⁸⁷º89¹⁰⁰⁺⁸⁷º89^j(125)+87º89^j(125) 89⁸⁷º1* 89⁸⁷º89⁸⁷ (mod 125). 

j(2³)= j(8)= 2³(1-¹/2)=4, НСД(89, 8)=1

89¹⁸⁷º89¹⁸⁴⁺³º89^4*46+3º89^{j(8) *46+3}º(89^j(8)) ⁴⁶ 89³º1* 89⁸⁷º89³º (88+1) ³ º 1³º 1(mod 8). 

Якщо  конгруенції справедливі за модулями 8 та 125 та

Тому дві останні цифри числа це 01, тобто 17⁴⁰=х*100+1.

89⁹⁸⁷=х(mod  1000)

Два прості числа V_p- та V_p+ вигляду називатимемо далекими близнюками, ящо кожне з них можна відповідно записати:

V_p- = 2^р-q  та  V_p+ = 2^р+q,

де р i q – прості числа.

Властивість: 1а) V_p+ - V_p- = 2^р+q - 2^р+q =2q- складене число;

1б) V_p+ +V_p- = 2^р+р + 2^р-р =2^р+1 -складене число;

2) V_p+ * V_p- = (2^р+q)(2^р-q) =4^р-q² -складене число;

Чи існує безліч далеких близнюків?

 вигляду:  V_p = 2^р-р 2^р-р, де р – просте число.

Гіпотеза: так, їх безліч!

Наприклад:  2³-3=5  і  2³+3=11, при цьому 11-5=2*3 

2¹³-13=8179 і 2¹³+13=11 

Узагальнення проблеми Кармайкла:

Нехай р, q – прості натуральні числа.  Четвірку чисел (р, q, s, t) - називатимемо вичурною квадрою, якщо для неї виконується рівність: 

p^qs -1= qt, де s, t - деякі натуральні числа.

Така вичурна квадра (41, 3, 2, 2735) існує:  

41^3*2-1=3*5*547

Добуток усіх дільників натурального числа m дорівнює  такому степеню:  число m в степені, що рівний половині від кількості усіх дільників. Наприклад: число 12 має 6 натуральних дільників, тоді добуток усіх його дільників обчислюється так 12 в степені 3(це 6:2), і це дорівнює 1728.