Oстанні цифри в десятковому запису степенів вигляду m^n.

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

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

Розв′язання. Cпочатку будемо вчитися. Для цього знайдемо помилку у наступному розв'язанні:

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

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

=1000*х +9³=1000*х +729, і це невірно! А чому? Правильна відповідь таки: 729. І немає нічого дивного. Маніпуляція з помилками і не більше! Розв'язання містить технічну помилку, а відповідь вийшла правильна!
 Проте!!! Розберемося. Зараз придивіться до останніх цифр.

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

19³=6*1000+859,  а

9⁹⁸⁷= 1000*х+769

89⁹⁸⁷=1000*у+729

109⁹⁸⁷=1000*у+469

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

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

Або

10..0089⁹⁸⁷=(1000m+089)⁹⁸⁷=1000*у+729

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

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

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

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

В)Функція Ейлера для натурального аргументу 1000: 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º704*1000+969º969(mod 1000). 

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