КЛАСИ ЛИШКІВ І КОНГРУЕНЦІЇ

КЛАСИ  ЛИШКІВ  І   КОНГРУЕНЦІЇ

На множині натуральних чисел виконуються операції додавання і множення, але не завжди виконується операція віднімання. Розширюючи множину N так, щоб арифметична операція віднімання завжди виконувалася, ми отримаємо множину цілих чисел Z. Тому Z=N È {0, -1, -2,...} або множина цілих містить цілі від’ємні числа(перед від’ємними числами завжди ставлять знак «мінус», нуль(це число, яке немає знаку) та цілі додатні числа(перед додатніми числами ставлять знак плюс або іноді нічого не ставлять): Z={...-3, -2, -1, 0, 1, 2, 3,...}, тобто, множина цілих чисел Z містить множину натуральних чисел, число нуль та числа, які протилежні натуральним(цілі від’ємні числа).

Зауваження. Впровадження нуля та від'ємних цілих чисел здійснено з метою запровадження дії віднімання, оберненої до додавання, так, щоб ре­зультат був завжди визначений. Це не потребує нових аксіом і здій­снено таким чином: множину натуральних чисел можна розширити до декартового добутку самої на себе з подальшою факторизацією – роз­биттям на класи еквівалентності.

Властивості додавання, множення та відношення порядку для множини цілих чисел ті самі, що й для множини натуральних чисел.

Головну роль у всій теорії цілих чисел відіграють наступні властивості чисел(далі ці властивості чисел сформульовані як теореми).  Ми наводимо їх без доведення.

Т е о р е м а  про  ділення  з  остачею. Для будь-якого цілого а і b > 0 існує і  притому  єдині цілі q та  r, такі, що

а = bq + r,                  де  0 £  r < | b |.

Зауваження: Ціле  число а називають ділене, ціле число b називають дільником, ціле число q – неповною часткою(результат дії ділення), число r називають остачею від ділення а: b.

Зауваження: Якщо ціле число  а ділиться на ціле число  b націло тоді внаслідок ділення отримуємо ціле число, тбто, повну частку, або   остача від ділення а:b  рівна нулю). Тому із умови подільності а:b  націло слідує, що існує деяке ціле число  z  таке,  що  а= z∙b.  

Приклад: Дію ділення 7:2=3(ост. 1) можна записати у такому вигляді:

7 = 2∙3 + 1,

де число 7 називають ділене, число 2 називають дільником числа 7, число 3 – неповною часткою(результат дії ділення), число 1 називають остачею від ділення 7: 2.

При діленні цілого числа на 7 можна отримати  7 різних  остач, тобто, 0, 1, 2, 3, 4, 5, 6.

Взагалі, якщо довільне  ціле число поділити на  натуральне m, то можна отримати m-1 остачу, тобто  0,  1, 2, 3, 4, 5, 6, …, m-1.  На основі цього можна множину  Z цілих чисел  можна розбити на m підмножин, які будемо позначати  Z_m (де m – ціле число, що змінюється від 0 до m-1). Розглянемо склад кожної такої підмножини:

Підмножина Z₀  складається з безлічі цілих чисел вигляду:

…, -3m, -2m, -m, 0, m, 2m, 3m, …,

 – це числа, які діляться націло на m. Цю підмножину називають  класом нульових лишків за модулем m. Усі числа класу Z₀ задовольняють рівняння в цілих числах:

x º 0(mod m),

цей вираз читають так: «ікс дорівнює нулю за модулем m», а такий

вираз  прийнято називати конгруенцією за модулем m. Тобто,

-3m º 0(mod m),

-2m  º 0(mod m),

-m º0(mod m),

m  º 0(mod m),

2m  º 0(mod m),

і так далі.

Підмножина Z₁  складається з безлічі цілих чисел вигляду:

…, -3m+1, -2m+1, -m+1, 1, m+1, 2m+1, 3m+1, …,

 – це числа, які при діленні  на m мають остачу(лишок) 1. Цю підмножину називають  класом одиничних лишків за модулем m. Усі числа класу Z₁ задовольняють рівняння в цілих числах:

x º 1(mod m),

яке  прийнято називати конгруенцією за модулем m. Тобто,

-3m+1 º 1(mod m),

-2m+1  º 1(mod m),

-m+1 º1(mod m),

m+1  º 1(mod m),

2m+1  º 1(mod m),

і так далі.

Підмножина Z₂  складається з безлічі цілих чисел вигляду:

…, -3m+2, -2m+2, -m+2, 2, m+2, 2m+2, 3m+2, …,

 – це числа, які при діленні  на m мають остачу(лишок) 2. Цю підмножину називають  класом двійкових лишків за модулем m.

Усі числа класу Z₂ задовольняють рівняння в цілих числах:

x º 2(mod m),

яке  прийнято називати конгруенцією за модулем m. Тобто,

-3m+2 º 2(mod m),

-2m+2  º 2(mod m),

-m+2 º2(mod m),

m+2  º 2(mod m),

2m+2  º 2(mod m),

і так далі.

Підмножина Z₃  складається з безлічі цілих чисел вигляду:

…, -3m+3, -2m+3, -m+3, 3, m+3, 2m+3, 3m+3, …,

 – це числа, які при діленні  на m мають остачу(лишок) 3. Цю підмножину називають  класом трійкових лишків за модулем m.

Усі числа класу Z₃ задовольняють рівняння в цілих числах:

x º 3(mod m),

яке  прийнято називати конгруенцією за модулем m. Тобто,

-3m+3 º 3(mod m),

-2m+3  º 3(mod m),

-m+3 º3(mod m),

m+3  º 3(mod m),

2m+3  º 3(mod m),

і так далі.

Підмножина Z₄  складається з безлічі цілих чисел вигляду:

…, -3m+4, -2m+4, -m+4, 4, m+4, 2m+4, 3m+4, …,

 – це числа, які при діленні  на m мають остачу(лишок) 4. Цю підмножину називають  класом четвіркових лишків за модулем m.

Усі числа класу Z₄ задовольняють рівняння в цілих числах:

x º 4(mod m),

яке  прийнято називати конгруенцією за модулем m. Тобто,

-3m+4 º 4(mod m),

-2m+4  º 4(mod m),

-m+4 º4(mod m),

m+4  º 4(mod m),

2m+4  º 4(mod m),

і так далі.

Зрозуміло, продовжуючи так далі, ми згодом отримаємо останню підмножину.

Підмножина Z_m-1  складається з безлічі цілих чисел вигляду:

…, -2m-1, -m-1, -1, m-1, 2m-1, 3m-1, 4m-1, …,

 – це числа, які при діленні  на m мають остачу(лишок) m-1. Цю підмножину називають  класом m-1-oкових лишків за модулем m.

Усі числа класу Z_m-1 задовольняють рівняння в цілих числах:

x º m-1(mod m),

яке  прийнято називати конгруенцією за модулем m. Тобто,

-3m-1 º m-1(mod m),

-2m-1  º m-1(mod m),

-m-1 ºm-1(mod m),

-1  º m-1(mod m),

m-1  º m-1(mod m),

і так далі.

Досить часто в математичній літературі зустрічається термін «множина цілих чисел розбита на класи еквівалентності за модулем m», цей термін відповідає  такому змісту, «множина цілих чисел розбита на класи лишків за модулем m».

Наведемо приклади у вигляді таблиці 

1)Класи лишків за модулем 6.

Зверніть увагу на те, що в кожному стовпчику  наведеної таблиці знаходяться числа тільки одного класу лишків за модулем 6.

Z0	Z1	Z2	Z3	Z4	Z5
6n-6	6n-5	6n-4	6n-3	6n-2	6n-1
…	…	…	…	…	…
-12	-11	-10	-9	-8	-7
-6	-5	-4	-3	-2	-1
0	1	2	3	4	5
6	7	8	9	10	11
12	13	14	15	16	17
18	19	20	21	22	23
24	25	26	27	28	29
…	…	…	…	…	…
6n	6n+1	6n+2	6n+3	6n+4	6n+5
Z0	Z1	Z2	Z3	Z4	Z5

Z0	Z1	Z2	Z3	Z4
5n-5	5n-4	5n-3	5n-2	5n-1
…	…	…	…	…
-10	-9	-8	-7	-6
-5	-4	-3	-2	-1
0	1	2	3	4
5	6	7	8	9
10	11	12	13	14
15	16	17	18	19
20	21	22	23	24
…	…	…	…	…
5n	5n+1	5n+2	5n+3	5n+4
Z0	Z1	Z2	Z3	Z4

Зауваження. У двох класах лишків Z₁(сюди входять числа вигляду 6n+1), Z₅(сюди входять числа вигляду 6n+5) за модулем 6  знаходяться прості числа, окрім двох простих чисел 2 та 3. Але в усіх класах лишків за модулем 6   можна знайти  складені числа.

2)Класи лишків за модулем 5.

Зверніть увагу на те, що в кожному стовпчику  наведеної таблиці знаходяться числа тільки одного класу лишків за модулем 5.

Зауваження. В усіх класах лишків за модулем 5   можна знайти  складені та прості числа.

1)Класи лишків за модулем 5.

Дії над класами лишків

Над класами лишків виконуються дії додавання і множення.

Так як множина ціліих чисел  складається з  m класів лишків, представниками яких є лишки 0, 1, 2, 3, 4      ,…,m-1.

Додавання класів виконуємо так, що знаходимо суму k+n представників цих класів і потім знаходимо лишок від ділення k+n на m, тобто,

k+n º r(mod m),

Елемент r, де  0<r<m-1, є представником відповідного класу лишків за модулем m.

Приклад: Додамо два представники із класів лишків Z₂ та  Z₅ за модулем 6.

6n+2 + 6n+5 = 12n+7 = 6∙2n +6+1= 6(2n+1)+1 = 6k+1.

Отримали в сумі представників із класу лишків Z₁ за модулем 6.

Аналогічно виконуємо множення класів .

Добуток k∙n виконуємо так, що знаходимо добуток k∙n представників цих класів і потім знаходимо лишок від ділення k∙n на m, тобто

k∙n º s(mod m),

 знаходимо лишок s за модулем m .

Елемент 0<s<m-1 є представником одного з класів лишків за модулем m.

Приклад: Помножимо два представники із класів лишків Z₂ та  Z₅ за модулем 6.

(6n+2)(6n+5) = (6n+2)∙6n+(6n+2)∙5 = 36n²+ 12n+30n+10 =

= 36 n²+ 42n+10 = 6∙6n +6∙7n + 6 + 4= 6(6n²+7n+1) + 4 = 6k+4.

Отримали в добутку представників із класу лишків Z₄ за модулем 6.

Вправи для самостійного осмислення.

1. Утворити класи лишків за модулем 2:

·         Знайти по одному найменшому від’ємному і додатному представнику з кожного класу;

_·          Знайти представника класів Z₁   та Z₀;

·         Виконати додавання та множення над представниками класу Z₁   та Z₀ і з’ясувати в якому класі знаходяться отримані сума та добуток.

2.      Утворити класи лишків за модулем 3. Знайти по одному найменшому від’ємному і додатному представнику з кожного класу;

_·          Знайти представника класів Z₁   та Z₂;

·         Виконати додавання та множення над представниками класу Z₁   та Z₂ і з’ясувати в якому класі знаходяться отримані сума та добуток.

3. Утворити класи лишків за модулем 4.

·         Знайти по одному найменшому від’ємному і додатному представнику з кожного класу;

_·          Знайти представника класів Z₁   та Z₃;

·         Виконати додавання та множення над представниками класу Z₂   та Z₃ і з’ясувати в якому класі знаходяться отримані сума та добуток.

4. Утворити класи лишків за модулем 7.

·         Знайти по одному найменшому від’ємному і додатному представнику з кожного класу;

_·          Знайти представника класів Z₃   та Z₆;

·         Виконати додавання та множення над представниками класу Z₄   та Z₁ і з’ясувати в якому класі знаходяться отримані сума та добуток.

5. Утворити класи лишків за модулем 8.

·         Знайти по одному найменшому від’ємному і додатному представнику з кожного класу;

_·          Знайти представника класів Z₁   та Z₀;

·         Виконати додавання та множення над представниками класу Z₁   та Z₀ і з’ясувати в якому класі знаходиться отримані сума та добуток.

6. Утворити класи лишків за модулем 9. Знайти по одному найменшому від’ємному і додатному представнику з кожного класу;

_·          Знайти представника класів Z₁   та Z₇;

·         Виконати додавання та множення над представниками класу Z₆   та Z₃ і з’ясувати в якому класі знаходиться отримані сума та добуток.

КОНГРУЕНТНІ ЧИСЛА ЗА МОДУЛЕМ 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 є представниками одного класу лишків, а конкретно Z₃.

Приклади конгруентних чисел за модулем 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, належать до одного й того самого класу чисел.

Отже, множину чисел розбиваємо на класи  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. Знайти останні дві цифри числа .

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.

Зауваження. Нехай натуральне число m, більше 2. Зрозуміло, що різні цілі числа при ділення на m можуть давати довільні із остач: 1,2, 3,4, …, m-1. Проте степені цілих чисел з фіксованим натуральним показником n>1 не обов’язково знову даватимуть при діленні на m будь-яку з цих остач.