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.

Відомі факти для подільності чисел.

Усі натуральні  числа можна записати так: 

а)   5k-2,  5k-1, 5k, 5k+1, 5k+2; 

б)  6k-3,  6k-2,  6k-1, 6k, 6k+1, 6k+2; 

Простими числами можуть бути числа вигляду: 6k-1 або 6k+1,  якщо k  – натуральне  число, до цих двох записів не потрапили прості числа 2 та 3, проте усі інші прості числа можна подати  у вигляді 6k-1 або 6k+1.

Подільність чисел, що мають представлення  у вигляді  цілого многочлена:

аb(а ± b)=2k – це парне число для довільних цілих  чисел  a i b.

аb(а⁴ –b⁴)=30k; 

n² –n =(n-1)n=2k;

n³ – n =(n-1)n(n+1)=6k;

n⁵ –n = (n-1)n(n+1)(n² +1)=5k; 

n⁷ –n =7k;   

(2k+1)² –(2n-1)² =8k;

n(n+1)= 2k, тобто, добуток двох послідовних цілих чисел завжди парне число;

(n+2)(n+1)n = 3k, тобто, добуток трьох послідовних цілих чисел завжди ділиться на 3 націло;

(n-1)n(n+1) = 6k, тобто, добуток трьох послідовних цілих чисел завжди ділиться на 6 націло;

(n-1)n(n+1)(n+2) = 12k тобто, добуток трьох послідовних цілих чисел завжди ділиться на 6 націло;

(n-2)(n-1)n(n+1)(n+2) = 2∙3∙4∙5k=120k, тобто, добуток п’яти послідовних цілих чисел завжди ділиться на 120 націло.

Для всіх простих чисел р> 2000 сума  1²⁰⁰⁰ + 2²⁰⁰⁰+3²⁰⁰⁰ +4²⁰⁰⁰ +…+(р-1)²⁰⁰⁰

ділиться на просте число р.

Мала теорема Ферма, яка стверджує, що якщо р- просте число, та натуральне число а таке, НСД(а; р)=1, тоді число

а^р-1-1 ділиться на просте число р,

або  цей факт можна записати у вигляді рівності конгруенції, яка виконується для простих чисел :

а^р-1º1(mod р).

До речі, існуюють такі складені числа m, що виконується мала теорема Ферма:

а^m-1-1 ділиться на cкладене число m,

 на приклад найменше складене число 561 таке, що

а^561-1-1ділиться націло на 561. І таких чисел безліч,ці числа – ще називають псевдопрості числа Кармайкла.

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

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

Мала теорема Ферма — одне з основних тверджень елементарної теорії чисел. Вперше була сформульована в листі французького математика П'єра де Ферма до свого друга Френікля де Бессі 18 жовтня 1640 року. В листі проте не було наведено доведення. Перше відоме доведення подане Лейбніцом у неопублікованих рукописах

Якщо n+1 –складене натуральне  число, то   число вигляду  1×2×3×4×5×…×(n-1) ×n =n!  ділиться на n.

Якщо n  – натуральне  число, що має непарний дільник,  то   число вигляду  2ⁿ +1  складене число.

Якщо n  – натуральне  число, то число вигляду  n⁸+4 - складене число.

Якщо n  – натуральне  число, то число вигляду  n⁸+ n⁴+1 - складене число.

(a - b)(a - c)(b - c)=  a²b -аb² + ac²- a²c  + b²c - bc²  - цей вираз завжди парне число,  якщо усі змінні – це  цілі числа.

(a + b)(a + c)(b + c)=  a²b +аb² + ac²+ a²c  + b²c + bc² +2abc;    - цей вираз завжди парне число,  якщо усі змінні – це  цілі числа.

(a - b)(a + c)(b - c)=  a²b -аb² - ac²- a²c  - b²c + bc² +2abc; - цей вираз завжди парне число,  якщо усі змінні – це  цілі числа.

 (a - b)(a + c)(b + c)=  a²b - аb² + ac²+ a²c  - b²c - bc²;  - цей вираз завжди парне число,  якщо усі змінні – це  цілі числа.  

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

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

Розв′язання.

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

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

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

Використаємо для цього властивості функції Ейлера 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.