Дії
над класами лишків
Над класами лишків виконуються дії додавання і множення.
Так як
множина ціліих чисел складається з m класів лишків, представниками яких є лишки 0, 1, 2, 3, 4 ,…,m-1.
Додавання класів
виконуємо так, що знаходимо суму k+n
представників цих класів і потім знаходимо
лишок від ділення k+n на m, тобто,
k+n º r(mod m),
Елемент r, де 0<r<m-1, є представником відповідного класу лишків за модулем m.
Приклад: Додамо
два представники із класів лишків Z2 та Z5 за модулем 6.
6n+2 + 6n+5 = 12n+7 = 6∙2n +6+1= 6(2n+1)+1 = 6k+1.
Отримали
в сумі представників із класу лишків Z1 за модулем 6.
Аналогічно
виконуємо множення класів .
Добуток k∙n виконуємо так, що знаходимо добуток k∙n представників цих класів і потім
знаходимо лишок від ділення k∙n на m, тобто
k∙n º s(mod m),
знаходимо лишок s за модулем m
.
Елемент 0<s<m-1
є представником одного з класів лишків за модулем m.
Приклад:
Помножимо два представники із класів лишків Z2 та Z5 за модулем 6.
(6n+2)(6n+5) = (6n+2)∙6n+(6n+2)∙5 = 36n2+ 12n+30n+10 =
= 36 n2+ 42n+10 = 6∙6n +6∙7n + 6 + 4= 6(6n2+7n+1) + 4 = 6k+4.
Отримали
в добутку представників із класу лишків Z4 за модулем 6.
Вправи для
самостійного осмислення.
1.
Утворити класи лишків за модулем 2:
·
Знайти по одному найменшому від’ємному і додатному представнику з кожного
класу;
·
Знайти представника класів Z1 та Z0;
·
Виконати додавання та множення над представниками класу Z1 та Z0 і
з’ясувати в якому класі знаходяться отримані сума та добуток.
2.
Утворити класи лишків за модулем 3. Знайти по одному найменшому від’ємному
і додатному представнику з кожного класу;
·
Знайти представника класів Z1 та Z2;
·
Виконати додавання та множення над представниками класу Z1 та Z2 і
з’ясувати в якому класі знаходяться отримані сума та добуток.
3.
Утворити класи лишків за модулем 4.
·
Знайти по одному найменшому від’ємному і додатному представнику з кожного
класу;
·
Знайти представника класів Z1 та Z3;
·
Виконати додавання та множення над представниками класу Z2 та Z3 і
з’ясувати в якому класі знаходяться отримані сума та добуток.
4.
Утворити класи лишків за модулем 7.
·
Знайти по одному найменшому від’ємному і додатному представнику з кожного
класу;
·
Знайти представника класів Z3 та Z6;
·
Виконати додавання та множення над представниками класу Z4 та Z1 і
з’ясувати в якому класі знаходяться отримані сума та добуток.
5.
Утворити класи лишків за модулем 8.
·
Знайти по одному найменшому від’ємному і додатному представнику з кожного
класу;
·
Знайти представника класів Z1 та Z0;
·
Виконати додавання та множення над представниками класу Z1 та Z0 і
з’ясувати в якому класі знаходиться отримані сума та добуток.
6. Утворити класи лишків за модулем 9. Знайти по одному
найменшому від’ємному і додатному представнику з кожного класу;
·
Знайти представника класів Z1 та Z7;
·
Виконати додавання та множення над представниками класу Z6 та Z3 і
з’ясувати в якому класі знаходиться отримані сума та добуток.
КОНГРУЕНТНІ ЧИСЛА ЗА МОДУЛЕМ 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 цього модуля.
місце за будь-яким дільником 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.
Китайська теорема про остачі. Якщо цілі числа m1, m2, m3, m4 , … , mk , то для довільних цілих чисел а1,
а2, а3, а4 , … , аk існує ціле число х, яке
задовольняє умови х º аі (mod mі), де i=1,k, При
цьому число х можна вважати числом, яке належить довільному наперед заданому
нівінтервалу довжиною, дорівнює добутку m1∙m2∙m3∙m4∙ … ∙mk.
Теорема.
Будь-яке натуральне число когруентне сумі своїх цифр у десятковій ситсемі
числення за модулем 9.
Зауваження.
Нехай натуральне число m, більше 2. Зрозуміло, що різні цілі числа при ділення на m можуть давати довільні із остач:
1,2, 3,4, …, m-1. Проте
степені цілих чиселз фіксованим натуральним показником n>1 не обов’язково знову даватимуть при діленні на m будь-яку з цих остач.
Немає коментарів:
Дописати коментар