неділя, 28 червня 2015 р.

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

Задача. Знаходження декількох останніх цифр в десятковому запису степенів вигляду mn.
Як знайти три останні цифри в десятковому запису степені 891203?
Розв′язання. Cпочатку будемо вчитися. Для цього знайдемо помилку у наступному розв'язанні:
(80+9) 987=(80+9) 3*7*47=
=(23*10+9) 3*7*47=((97)47)3= (10у+9)3=
=1000*х +93=1000*х +729, і це невірно! А чому? Правильна відповідь таки: 729. І немає нічого дивного. Маніпуляція з помилками і не більше! Розв'язання містить технічну помилку, а відповідь вийшла правильна!
 Проте!!! Розберемося. Зараз придивіться до останніх цифр.
Зверніть увагу на такі правильні вирази:
193=6*1000+859,  а
9987= 1000*х+769
89987=1000*у+729
109987=1000*у+469
Висновок: Не можна користуватися методом (10*у+х)m для знаходження останніх трьох цифр. Тут варто користуватися розкладом: (1000*у+х)m  і потім досліджувати останні цифри лишку, тобто числа: хm

Наприклад, 10000...009987=(1000*у+9)987   і досліджувати останні цифри числа: 9987. Отже, 1000*х+769
Або
10..0089987=(1000m+089)987=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) (1-1/р2)…( 1-1/рk),
де {рі і=1..k},– це усі прості числа, які є дільниками числа m.
Наприклад, а)j(10)= 10(1-1/2) (1- 1/5)= =10*0,5*0,8 = 4.
б)j(100)= 100(1-1/2) (1-1/5)=100*0,5*0,8 =40.
в)j(1000)= 1000(1-1/2) (1-1/5)=1000*0,5*0,8= =400.
г)j(10000)= 10000*(1-1/2)*(1-1/5) = =10000*0,5*0,8 =4000.
Д) j(10n)= 10n(1-1/2) (1-1/5)= 10n *0,5*0,8 =4*10n-1.
Нам треба для обчислення, що твердження теореми Ейлера: Якщо  m>1,  НСД(a, m) =1 справедлива конгруенція aj(m) º1(mod m),  де j(m) – функція Ейлера.

Наприклад. А) Не виконуючи великих і складних обчислень, можна знайти чотири останні цифри неймовірно великого числа 34000. Для цього варто скористатися теоремою Ейлера: 3j(10000) º1(mod 10000),  бо НСД(3, 10000) =1, тому 34000 º1(mod 10000).  Тому чотири останні цифри числа це 0001, тобто 34000=х*10000+1.
Б) Не виконуючи великих і складних обчислень, можна знайти дві останні цифри великого числа 1740. Для цього варто скористатися теоремою Ейлера:
j(100)= 100(1-1/2)(1-1/5)=100*0,5*0,8  =40.
НСД(17, 100)=1
1740º17j(100) º1(mod 100).  Тому дві останні цифри числа це 01, тобто 1740=х*100+1.
А тепер реальна задача:
Як знайти три останні цифри в десятковому запису степені 891203ºх(mod 1000)?
Для цього варто скористатися теоремою Ейлера:
j(1000)= 1000(1-1/2)(1-1/5)=1000*0,5*0,8=400.
НСД(89, 1000)=1
891203º89400+400+400+3º89j(1000) 89j(1000) 89j(1000) 893 º1*1*893º893º704969º704*1000+969º969(mod 1000). 
Тому три останні цифри числа це 969.

пʼятниця, 26 червня 2015 р.

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


Усі натуральні  числа можна записати так: 
а)   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(а4 b4)=30k
n2 n =(n-1)n=2k;
n3 – n =(n-1)n(n+1)=6k;
n5 n(n-1)n(n+1)(n2 +1)=5k
n7 n =7k;   

(2k+1)2 (2n-1)2 =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 сума  12000 + 22000+32000 +42000 +…+(р-1)2000
ділиться на просте число р.
Мала теорема Ферма, яка стверджує, що якщо р- просте число, та натуральне число а таке, НСД(а; р)=1, тоді число
ар-1-1 ділиться на просте число р,
або  цей факт можна записати у вигляді рівності конгруенції, яка виконується для простих чисел :
ар-1º1(mod р).
До речі, існуюють такі складені числа m, що виконується мала теорема Ферма:
аm-1-1 ділиться на cкладене число m,
 на приклад найменше складене число 561 таке, що
а561-1-1ділиться націло на 561. І таких чисел безліч,ці числа – ще називають псевдопрості числа Кармайкла.
Теорема Ейлера. Якщо  m>1,  НСД(a, m) =1 справедлива конгруенція aj(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  – натуральне  число, що має непарний дільник,  то   число вигляду  2n +1  складене число.
Якщо n  – натуральне  число, то число вигляду  n8+4 - складене число.
Якщо n  – натуральне  число, то число вигляду  n8+ n4+1 - складене число.
(a - b)(a - c)(b - c)=  a2b -аb2 + ac2- a2c  + b2c - bc2  - цей вираз завжди парне число,  якщо усі змінніце  цілі числа.
(a + b)(a + c)(b + c)=  a2b +аb2 + ac2+ a2c  + b2c + bc2 +2abc;    - цей вираз завжди парне число,  якщо усі змінніце  цілі числа.
(a - b)(a + c)(b - c)=  a2b -аb2 - ac2- a2c  - b2c + bc2 +2abc; - цей вираз завжди парне число,  якщо усі змінніце  цілі числа.

 (a - b)(a + c)(b + c)=  a2b - аb2 + ac2+ a2c  - b2c - bc2;  - цей вираз завжди парне число,  якщо усі змінніце  цілі числа.  

Задача. Знаходження декількох останніх цифр в десятковому запису степенів вигляду mn.
Як знайти три останні цифри в десятковому запису степені 89987?
Розв′язання.
(80+9) 987=(80+9) 3*7*47=
=(23*10+9) 3*7*47=((97)47)3= (10у+9)3=
=1000*х +93=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) (1-1/р2)…( 1-1/рk),
де {рі і=1..k},– це усі прості числа, які є дільниками числа m.
Наприклад, а)j(10)= 10(1-1/2) (1- 1/5)= =10*0,5*0,8 = 4.
б)j(100)= 100(1-1/2) (1-1/5)=100*0,5*0,8 =40.
в)j(1000)= 1000(1-1/2) (1-1/5)=1000*0,5*0,8= =400.
г)j(10000)= 10000*(1-1/2)*(1-1/5) = =10000*0,5*0,8 =4000.
Д) j(10n)= 10n(1-1/2) (1-1/5)= 10n *0,5*0,8 =4*10n-1.
Нам треба для обчислення, що твердження теореми Ейлера: Якщо  m>1,  НСД(a, m) =1 справедлива конгруенція aj(m) º1(mod m),  де j(m) – функція Ейлера.

Наприклад. А) Не виконуючи великих і складних обчислень, можна знайти чотири останні цифри неймовірно великого числа 34000. Для цього варто скористатися теоремою Ейлера: 3j(10000) º1(mod 10000),  бо НСД(3, 10000) =1, тому 34000 º1(mod 10000).  Тому чотири останні цифри числа це 0001, тобто 34000=х*10000+1.
Б) Не виконуючи великих і складних обчислень, можна знайти дві останні цифри великого числа 1740. Для цього варто скористатися теоремою Ейлера:
j(100)= 100(1-1/2)(1-1/5)=100*0,5*0,8  =40.
НСД(17, 100)=1
1740º17j(100) º1(mod 100).  Тому дві останні цифри числа це 01, тобто 1740=х*100+1.
Як знайти три останні цифри в десятковому запису степені 891203ºх(mod 1000)?
Для цього варто скористатися теоремою Ейлера:
j(1000)= 1000(1-1/2)(1-1/5)=1000*0,5*0,8=400.
НСД(89, 1000)=1
891203º89400+400+400+3º89j(1000) 89j(1000) 89j(1000) 893  º1*1*893º893º704969º969(mod 1000). 
Тому три останні цифри числа це 969.