Таблиця Вінницького довжини двоцифрових періодів степенів цифр.

ВЛАСТИВОСТІ КОНГРУЕНТНИХ ЧИСЕЛ

1. Два цілих числа, які конгруентні третьому за модулем m, конгруентні між собою за цим самим модулем.

Якщо

а ºb (mod m),

с º b (mod m)

то

а º с (mod m).

Зауваження. У конгруенції будь-яке число можна замінити конгруентним йому.

Наприклад,

5 = 2 (mod 3),

5 = 8 (mod 3) .

Отже,

8 = 2 (mod 3).

2. Числа, конгруентні за модулем m, належать до одного й того самого класу чисел.  Отже, множину чисел розбиваємо на класи  Z_r за модулем m.
Всіх класів буде m, їх позначають:  Z₀, Z₁, Z₂, _{, …,} Z_m-1.

3. Конгруенції за одним і тим самим модулем можна почленно додавати або віднімати.

Наприклад,

а º b (mod m).

c º d (mod m).

а±c º b±d (mod m).

4.  Конгруенції за одним і тим самим модулем можна почленно множити.

Наприклад,

а º b (mod m).

c º d (mod m).

а∙c º b∙d (mod m).

5. Члени конгруенції можна переносити з однієї частини в другу, змінюючи їх знак на протилежний.

Якщо

а º b + с(mod m),

то також вірно

а-с º b (mod m),

або

а-b º с (mod m),

або

а - b- c º 0 (mod m).

6. До кожної з частин конгруенції можна додати (або відняти) число, кратне модулю.

Якщо

а º  b (mod m),

то

а + km º  b (mod m)

а º  b + km (mod m),

або

а - km º  b (mod m)

а º  b - km (mod m).

7. Обидві частини конгруенції можна помножити на одне й те саме ціле число.

Якщо

а º b (mod m),

то

аk º bk (mod m),

де k – ціле число.

8.  Обидві частини конгруенції можна піднести до одного й того самого степеня, показник якого є ціле невід'ємне число.

Якщо

 а º b (mod m),

то

а^k º b^k (mod m),

                       

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

Якщо

а º b (mod m),

 НСД(k, m)=1, то

a:k º b:k (mod m),

10. Обидві частини конгруенції і модуль можна помножити на одне й те саме натуральне число.

Якщо

а º b (mod m),

то

аk º bk (mod km),

11.  Обидві частини конгруенції і модуль можна поділити на будь-який їх спільний дільник.

Якщо

а º b (mod m),

то

а:k º b:k (mod m:k),

12. Якщо конгруенція має місце за модулем m, то вона матиме місце за будь-яким дільником k¹1 цього модуля.

а º b (mod m),

то

а º b (mod k),

13.  Якщо конгруенція має місце за кількома модулями, то вона матиме місце і за модулем, що дорівнює їх найменшому спільному кратному:  НСК (m;n) = k.

Якщо

a º b (mod m),

а º b (mod n),

то

а º b (mod k).

14. Якщо одна частина конгруенції і модуль діляться на яке-небудь ціле число, то й друга частина конгруенції повинна ділитись на це число.

15. Якщо в многочлені f(х₁ х₂,..., х_n) від n цілих величин х₁ х₂,..., х_n з цілими коефіцієнтами ці величини і коефіцієнти замінити конгруентними з ними величинами і числами за модулем m, то в результаті дістанемо новий многочлен, конгруентний з попереднім за тим самим модулем m.

16. Китайська теорема про остачі. Якщо цілі числа m₁, m₂, m₃, m₄ , … , m_{k ,} то для довільних цілих чисел а₁, а₂, а₃, а₄ , … , а_k існує ціле число х, яке задовольняє умови х º а_і (mod m_і), де i=1,k,  При цьому число х можна вважати числом, яке належить довільному наперед заданому півінтервалу довжиною, дорівнює добутку  m₁∙m₂∙m₃∙m₄∙ … ∙m_k.

17. Теорема. Будь-яке натуральне число когруентне сумі своїх цифр у десятковій системі числення за модулем 9.

18. Теорема Ейлера. Функція кількості взаємно простих чисел для натурального числа n називається функцією Ейлера j(n), для неї виконується конгруенція

a^j(n)º1(mod n).

20. Теорема Ферма.  Для простого числа р виконується конгруенція

а^р-1º1(mod р)

або

а^рºа(mod р).

Задачі для самостійного осмислення.

1. Знайти остачу відділення 9⁴⁵+17 на 56.
2. Знайти остачу від ділення 7⁵⁰+3 на 43.
3. Знайти остачу від ділення 8¹⁰⁰+11¹⁰⁰ на 19.
4. Довести, що вираз 6⁵⁰+7²⁵ ділиться без остачі на 11.
5. Знайти останні три цифри числа 123⁴⁰².
6. Знайти останні дві цифри числа 3
7. Знайти останні дві цифри числа 4    .
8. Довести, що вираз 8¹⁶+8 ділиться без остачі на число 19.
9. Знайти останні  цифри числа  a+b+ab.

10.          Довести, що вираз 4²⁰+4² ділиться без остачі на число 17.

11.         Знайти таке а, при якому вираз 5²⁴+7а ділиться без остачі на число 23.

12.         Знайти остачу від ділення 9⁹⁵+27 на 89.

13.         Довести, що остача від ділення 3¹⁹+5⁴⁸ на 23 дорівнює 10.

14.         Довести, що остача від ділення 7∙5⁶+21 на 29 дорівнює 8.

15.         Довести, що остача від ділення 8∙12⁸+3 на 23 дорівнює 21.

16.         Довести, що остача від ділення 9∙15¹¹+2 на 37 дорівнює 25.

      17. Довести, що остача відділення 17∙14⁹+5 на 45 дорівнює 33.

Таблиця Вінницького довжини двоцифрових періодів степенів цифр.

(Степеневі лишки при діленні на 100)

m^{n  =} ab(mod 100).

Основа	2	3	4	5	6	7	8	9
Довжина  двоцифрового періоду  ….аb	20(поч. з 04)	20	10	1	5	4	20	10
Довжина  одноцифрового періоду  ….аb	4	4	2	1	1	4	4	2
Критерій парності двох цифр лишку	k & 2n	2k & 2n+1	k & 2n	2k & 2n+1	2k+1&2n	2k & 2n+1	k & 2n	2k & 2n+1
m1	02	03	04	05	06	07	08	09
m2	04	09	16	25	36	49	64	81
m3	08	27	64	25	16	43	12	29
m4	16	81	56	25	96	01	96	61
m5	32	43	24	25	76	07	68	49
m6	64	29	96	25	56	49	44	41
m7	28	87	84	25	36	43	52	69
m8	56	61	36	25	16	01	16	21
m9	12	83	44	25	96	07	28	89
m10	24	49	76	25	76	49	24	01
m11	48	47	04	25	56	43	92	09
m12	96	41	16	25	36	01	36	81
m13	92	23	64	25	16	07	88	29
m14	84	69	56	25	96	49	04	61
m15	68	07	24	25	76	43	32	49
m16	36	21	96	25	56	01	56	41
m17	72	63	84	25	36	07	48	69
m18	44	89	36	25	16	49	84	21
m19	88	67	44	25	96	43	72	89
m20	76	01	76	25	76	01	76	01
m21	52	03	04	25	56	07	08	09

Отже, можливі тільки такі степеневі двоцифрові лишки  для степенів цифр: 00, 01,  02, 03, 04, 05, 06, 07, 08, 09, 12,16, 21,23, 24, 25, 27, 28, 29, 32, 36, 41, 43, 44, 47, 48, 49, 52,56, 61, 63, 64, 67, 68, 69, 72,76, 81,83,  84, 88, 89, 92, 96.

Квадратні лишки.  Остачі при діленні квадратів на натуральні числа.

Якщо квадрат натурального числа, тобто,  m² = m∙m, поділити на:  2, то отримаємо остачі 0, 1;  на 3, то отримаємо остачі 0, 1;  на 4, то отримаємо остачі 0, 1;  на 5, то отримаємо остачі 0, 1, 4; на 6, то отримаємо остачі 0, 1, 3, 4; на 7, то отримаємо остачі  0, 1, 2, 4; на 8, то отримаємо остачі  0, 1, 4; на  9, то отримаємо остачі 0, 1, 4, 7; на 10, то отримаємо остачі 0, 1, 4, 5, 6, 9; на 11, то отримаємо остачі 0, 1, 3, 4, 5, 9;  на 12, то отримаємо остачі 0, 1, 4, 9;   на 13, то отримаємо остачі 0, 1, 3, 4, 9, 10, 12;  на 14, то отримаємо остачі 0, 1, 2, 4, 8, 9;  на 15, то отримаємо остачі 0, 1,4, 6,  9, 10;  на 16, то отримаємо остачі 0, 1, 4, 9;  на 17, то  отримаємо остачі 0, 1, 4, 8, 9,15.

Кубічні лишки. Остачі при діленні кубів на натуральні числа.

Якщо куб натурального числа, тобто,  m³ = m∙m∙m, поділити на:  2, то отримаємо остачі 0, 1; на 3, то отримаємо остачі 0, 1, 2; на 4, то отримаємо остачі 0, 1, 3; на 5, то отримаємо остачі 0, 1, 2, 3, 4;

6, то отримаємо остачі 0, 1, 2, 3, 4, 5; на 7, то отримаємо остачі  0, 1, 6; на 8, то отримаємо остачі  0, 1, 3, 5, 7; на 9, то отримаємо остачі  0, 1, 8; на 10, то отримаємо остачі 0, 1, 2, 3, 4, 5; 6; 7; 8; 9.

Четвіркові лишки. Остачі при діленні четвертих степенів на натуральні числа.

Якщо четверту степінь натурального числа, тобто,  m⁴ = m∙m∙m∙m, поділити на:  2, то отримаємо остачі 0, 1;

на  3, то отримаємо остачі 0, 1; на 4, то отримаємо остачі 0, 1; на 5, то отримаємо остачі 0, 1; на  6, то отримаємо остачі 0, 1, 3, 4; на 7, то отримаємо остачі  0, 1, 2, 4; на 8, то отримаємо остачі  0, 1; на 9, то отримаємо остачі 0, 1, 4, 7; на 10, то отримаємо остачі 0, 1, 5, 6.

П’ятіркові лишки. Остачі при діленні п’ятих степенів на натуральні числа.

Якщо п’яту степінь натурального числа, тобто,  m⁵ = m∙m∙m∙m∙m, поділити на:  2, то отримаємо остачі 0, 1;

на 3, то отримаємо остачі 0, 1, 2; на 4, то отримаємо остачі 0, 1, 3; на 5, то отримаємо остачі 0, 1, 2, 3, 4;

на 6, то отримаємо остачі 0, 1, 2, 3, 4, 5; на 7, то отримаємо остачі  0, 1, 2, 3, 4, 5, 6; на 8, то отримаємо остачі  0, 1, 3, 5, 7; на 9, то отримаємо остачі  0, 1, 2, 4, 5, 7, 8; на 10, то отримаємо остачі 0, 1, 2, 3, 4, 5; 6; 7; 8; 9.