КОНГРУЕНТНІ ЧИСЛА ЗА МОДУЛЕМ m
ТА ЇХНІ ВЛАСТИВОСТІ.
Означення. Два цілих числа а і b називаються конгруентними за
модулем m, якщо числа а і b при діленні на m дають однакові остачі.
Конгруентні числа за модулем m можна записати у вигляді:
a = mg+r,
b = mk+r,
де 0<r<m.
Модуль m є натуральним числом.
Конгруентність
за
модулем m
чисел a та b записуємо так:
а º b (mod m).
Конгруентність чисел
а і b за модулем m рівнозначна:
а) рівності а = b+mk,
де k=0, ± 1, ± 2, ... ;
б) подільності а-b на m;
тобто, а-b ділиться націло на m.
Приклади
конгруентних чисел за модулем 5
-7 º -2 (mod 5).
3 º 8 (mod 5).
13 º -12 (mod 5).
5 º 0 (mod 5).
Перевірити конгруентність за модулем 5 можна таким чином, відняти від лівої
частини конгруенції -7 праву частину
конгруенції -2, тобто -7-(-2)=-5, це число ділиться націло на 5. Отже
числа -7 та -2 є представниками одного класу лишків, а конкретно Z3.
Приклади
конгруентних чисел за модулем 7
6 º -1 (mod 7).
-4 º 3 (mod 7).
13 º 6 (mod 7).
7 º 0 (mod 7).
Властивості
конгруентних чисел
1. Два цілих числа,
які конгруентні третьому за модулем m,
конгруентні між собою за цим самим модулем.
Якщо
а ºb (mod m),
с º b
(mod m)
то
а º с (mod m).
Зауваження.
У конгруенції будь-яке число
можна замінити конгруентним йому.
Наприклад,
5 = 2 (mod 3),
5 = 8 (mod 3) .
Отже,
8 = 2 (mod 3).
2. Числа, конгруентні
за модулем m, належать до одного й
того самого класу чисел.
Отже, множину чисел
розбиваємо на класи Zr за модулем m.
Всіх класів буде m Z0, Z1, Z2, , …, Zm-1.
Всіх класів буде m Z0, Z1, Z2, , …, Zm-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
º bk (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(х1 х2,..., хn) від n цілих величин х1 х2,..., хn з цілими коефіцієнтами ці величини і
коефіцієнти замінити конгруентними з ними величинами і числами за модулем m, то в результаті дістанемо новий многочлен,
конгруентний з попереднім за тим самим модулем m.
16. Китайська теорема про остачі. Якщо цілі числа m1, m2, m3, m4 , … , mk , то для довільних цілих чисел а1,
а2, а3, а4 , … , аk існує ціле число х, яке
задовольняє умови х º аі (mod mі), де i=1,k, При
цьому число х можна вважати числом, яке належить довільному наперед заданому півінтервалу
довжиною, дорівнює добутку m1∙m2∙m3∙m4∙ … ∙mk.
17. Теорема.
Будь-яке натуральне число когруентне сумі своїх цифр у десятковій системі
числення за модулем 9.
18. Теорема Ейлера. Функція кількості взаємно простих чисел для натурального числа n називається функцією Ейлера j(n), для неї виконується конгруенція
aj(n)º1(mod n).
20. Теорема Ферма. Для простого числа р виконується
конгруенція
ар-1º1(mod р)
або
арºа(mod р).
Задачі для самостійного осмислення.
- Знайти остачу відділення 945+17
на 56.
- Знайти остачу від ділення 750+3
на 43.
- Знайти остачу від ділення 8100+11100
на 19.
- Довести, що вираз 650+725
ділиться без остачі на 11.
- Знайти останні три цифри числа 123402..
- Довести, що вираз 816+8 ділиться без остачі на число 19.
7.
Довести, що вираз 420+42
ділиться без остачі на число 17.
8.
Знайти
таке а, при якому вираз 524+7а ділиться без остачі на число 23.
9.
Знайти
остачу від ділення 995+27 на 89.
10.
Довести,
що остача від ділення 319+548 на 23 дорівнює 10.
11.
Довести,
що остача від ділення 7∙56+21 на 29
дорівнює 8.
12.
Довести,
що остача від ділення 8∙128+3 на 23 дорівнює 21.
13.
Довести,
що остача від ділення 9∙1511+2 на 37
дорівнює 25.
14. Довести, що остача відділення 17∙149+5 на 45 дорівнює
33.
Зауваження.
Нехай натуральне число m, більше 2. Зрозуміло, що різні цілі числа при ділення на m можуть давати довільні із остач:
1,2, 3,4, …, m-1. Проте
степені цілих чисел з фіксованим натуральним показником n>1 не обов’язково знову даватимуть при діленні на m будь-яку з цих остач.
ао
ВідповістиВидалити