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

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

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