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

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

На множині натуральних чисел виконуються операції додавання і множення, але не завжди виконується операція віднімання. Розширюючи множину 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

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

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

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

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

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

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

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

3)Запишемо повну множину усіх  остач при діленні цілочисельного виразу  х²+у² на 7. Складемо для цього таблицю остач:(тотожні перетворення виразів для отримання лишків виконайте самостійно)

х2+у2	х=7m-3	х=7m-2	х=7m-1	х=7m	х=7m+1	х=7m+2	х=7m+3
у=7k-3	7р+4	7р+6	7р+3	7р+2	7р+3	7р+6	7р+4
у=7k-2	7р+6	7р+1	7р+5	7р+4	7р+5	7р+1	7р+6
у=7k -1	7р+3	7р+5	7р+2	7р+1	7р+2	7р+5	7р+3
у=7k	7р+2	7р+4	7р+1	7р	7р+1	7р+4	7р+2
у=7k +1	7р+3	7р+5	7р+2	7р+1	7р+2	7р+5	7р+3
у=7k +2	7р+6	7р+1	7р+1	7р	7р+1	7р+4	7р+6
у=7k +3	7р+4	7р+6	7р+3	7р+2	7р+3	7р+6	7р+4

Проаналізувавши цю таблицю, маємо тільки один випадок, коли цілочисельний вираз х²+у² ділиться націло на 7, тобто х=7m,  у=7k. Таким чином, цілочисельний вираз х²+у² поділиться на 49 тоді і тільки тоді,  коли х=7m,  у=7k.

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

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

Так як множина ціліих чисел  складається з  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₃ і з’ясувати в якому класі знаходиться отримані сума та добуток.