Теорія чисел в криптографії

Питання 3. Приклади мультиплікативних функцій.

Приклад 1.
Кількість дільників числа a = p α1		× p	α2	×...× p	αk .
	1		2		k
Введемо мультиплікативну функцію				f (a) =1 . Розглянемо для цієї функції 3-ю
властивість мультиплікативних функцій:
Ліва частина: ∑ f (d ) = ∑1 = 1 +1 +1... - кількість дільників числа a
D|a	D|a
Права частина: (1 + a1 )(1 + a2 )...(1+ ak ),
Отже, кількість дільників числа a		дорівнює добутку степенів усіх простих чисел, що

входять до канонічного розкладу числа, збільшених на 1. Позначимо функцію визначення кількості дільників числа, як t(a) . Тоді:

t(a) = (1 + a1 )(1 + a2 )...(1 + ak )

t(a) - мультиплікативна функція, для якої кількість дільників числа a = pα , за умови, що α > 0 , p - просте число, дорівнює

t(pα )= (a +1)

Приклад.

Знайти кількість дільників числа 1. a = 24 ×5 ×73 ×19 ; 2. a = 84 = 22 ×3 × 7

Розв’язання: 1. t(a) = 5 × 2 × 4 × 2 = 80 ; 2. t(a) = 3 × 2 ××2 = 12 ,

Приклад 2.

Сума додатних дільників числа a = p1α1 × p2 α2 ×...× pk αk .

Введемо мультиплікативну функцію f (a) = a і підставимо її у властивість 3. Будемо

мати:

∑ d = (1+ p1 + p12 + ...+ p1α1 )(1+ p2 + p2 2 + ...+ p2α2 )× ...× (1+ pk + pk 2 + ...+ pk αk )

D|a

Ліворуч у формулі стоїть сума усіх додатніх дільників числа a . Позначимо цю суму S (a) . Праворуч у дужках маємо суми геометричних прогресій із знаменниками

. Використовуючи формулу суми геометричної прогресії для n = ai +1, (i =

)

p1 , p2 ,..., pk

1, k

членів, отримаємо:

S (a) =

1 - p

α1 +1

1 - p α2 +1

×...×

1 - p

αk +1

1

×

2

k

, або

1 - p1

1- p2

1- pk

S (p α1

× p

α2

×...× p

αk )=

p1

α1 +1 -1

×

p2

α2 +1 -1

×...×

pk αk +1 -1

2

k

1

p1

-1

p2 -1

pk -1

S (a) - мультиплікативна функція,

для якої, за умови, що α > 0 , сума додатніх

дільників числа a = pα

дорівнює:

S (pα )= pα+1 -1 p -1

21

Приклад.
Знайти суму дільників числа 1.								a = 24 ×5 ×73 ×19 ; 2.									a = 84 = 22 ×3 × 7
Розв’язання: 1. S (24 ×5 ×73 ×19)=							25 -1			×	52 -1			×	74 -1	×	192 -1	= 1488000 ;
																	18
2. S (22 ×3 × 7)=								1				4		6
	23 -1	×	32 -1	×	72 -1	=			5 ×8 × 48				= 160 ,
1		2		6				12				S (a) пов’язаний певний якісний аналіз числа a .
З функцією суми дільників числа a -

Сума власних додатних дільників числа a може бути:

1.менша, ніж саме число a , число a в цьому разі носить назву „ недостатнє” число;

2.більша, ніж саме число a , тоді a - „ надлишкове” число;

3.в окремих випадках – рівна самому числу a .

З самим числом a повна сума додатних дільників числа a буде в цьому випадку дорівнювати 2a .

Числа, для яких S (a) = 2a носять назву „ досконалі” числа. Для досконалих чисел вірна теорема:

Число a буде досконалим тоді і тільки тоді, коли воно має вигляд a = 2k −1 (2k -1); k ³ 2;

(2k -1) - просте число.

В теорії чисел доводиться, що число (2k -1) буде простим тільки, коли k є простим число. Числа (2k -1) в теорії чисел носять назву прості числа Мерсенна.

Кожне число Мерсенна відповідає новому досконалому парному числу. Приклад.

Візьмемо k = 7 P = 27 -1 =127 - просте число Мерсенна. a = 26 (27 -1)= 26 ×127 = 8128

Кількість додатних дільників числа обчислимо за формулою:

S (a) =	27 -1	×	1272 -1	=	127 ×(1272 -1) =		127 ×(127 - 1)(127 +1)		=127 ×128 = 2 × 26 ×127 = 2a
2 -1 126						126		126
Таким чином число a = 8128 є досконалим числом, бо S (8128) = 2 ×8128 , або S (a) = 2a
Інколи розглядаються в теорії чисел і так звані „ дружні числа” .
Дружніми числами називається пара чисел a ,b , якщо
S (a) = b & S (b) = a
Тобто сума додатних дільників числа								a дорівнює b і сума додатних дільників
числа b дорівнює a .
Приклад 3.
Функція Ейлера та її властивості.
Означення. Функція Ейлера визначає								для довільного цілого додатного числа		a
кількість чисел з ряду цілих 0 £ bi £ a -1,								взаємно простих з числом a , тобто таких,		що
(a,bi ) = 1.
Позначається функція Ейлера: j(a).
Приклади: j(1) =1 - за означенням.

a = 2, j(2) =1 - перед 2 є одне просте число – 1.

22

a = 3, j(3) = 2 - взаємно прості з 3 – 1,2 a = 4, j(4) = 2 - взаємно прості з 4 – 1,3

a = 5, ϕ (5) = 4 - взаємно прості з 5 – 1,2,3,4

a =13, j(13) =12 - оскільки 13 – просте, то увесь ряд чисел до цього числа є взаємно

простий з ним.

Функція Ейлера для простого числа та для числа, яке є степенем простого числа:

1. для a = p - простого числа -

j(p) = p1 - p0 = p -1

j(p) = p

1

2. для a = pα

- степеня простого числа -

α 1

-

= p

α - pα−1

p

Функція Ейлера є мультиплікативною функцією.

Розглянемо канонічне подання довільного цілого

a = p α1

× p

α2

×...× p

αk . Для довільного

1

2

k

цілого функція Ейлера буде мати вигляд:

α1

α2

αk

1

1

1

j(a) = j(p1

× p2

×... × pk

-

-

, або

)= a × 1

1

... 1 -

p1

p2

pk

j(a) = (p α1

- p α1 −1 )(p

α2

- p

α2 −1 )...(p

αk

- p

αk −1 )

1

1

2

2

k

k

Приклади:

j(28) = j(22 )j(7) = (22 - 2)(7 -1) = 12,

це (1,3,5,9,11,13,15,17,19, 23, 25, 27)

j(101) = 100;

j(225) = (32 - 3)(52 - 5)= 6 × 20 = 120

α1 × p

α2 × ...× p

αk :

Розглянемо усі дільники для довільного цілого числа a = p

2

= p β1 × p

β2

βk ;

1,t(a);

1

k

× ...× p

0 £ b

£ a

i =

j =

d

i

j

j

;

1,k

1

2

k

Кожний дільник є цілим числом, до якого можна застосувати функцію Ейлера:

j(di ); i =1,t(a)

Вірною є така теорема:

∑ j(d ) = a

D|a

		Тобто				кількість				чисел		взаємнопростих			з	кожним		із дільників числа
a = p		α1 × p		α2	× ...× p		αk	дорівнює самому числу a .
1				2			k
Приклад:
Розглянемо число 48.
48 = 243;					t(48) = 5 × 2 =10
	d		1			2			3		4	6		8	12		16	24		48
	j(d )		1			1			2		2	2		4	4		8	8		16
∑j(d ) = 1+1+ 2 + 2 + 2 + 4 + 4 + 8 + 8 +16 = 48
D|a
3. Розглянемо довільне натуральне число a . Розглянемо його дільник d .
Для цієї пари вірним буде таке:
Кількість натуральних чисел mi ,													які не перевищують число a , ( mi						£ a ), і мають з

цим числом найбільший спільний дільник d , тобто (a ,mi ) = d , дорівнює

23

= j a k d

Приклад.

Знайти кількість натуральних чисел, менших за a = 450 і таких що мають з цим числом спільний дільник d = 15

Розв’язання.

a = 450 =

30

d 15

Отже кількість чисел, менших за 450 і таких, що мають НСД з 450 рівним 15, буде k = j(30) = j(2 ×3×5) = (2 -1)(3 -1)(5 -1) = 8

Висновки Після вивчення теми 2 ви повинні знати такі факти:

-функція виділення цілої частини дійсного числа х повертає найбільше ціле число, яке не перевищує х,;

-функція виділення дробової частини дійсного числа х повертає різницю між числом х та його цілою частиною;

-функція f (a) називається мультиплікативною, якщо для неї виконуються 2

умови:
1. f (a) визначена для усіх a = 0,1,2... і хоча б для одного a0						f (a0 ) = 0 .
2. Для будь-яких a1 ,			a2 : (a1 , a2 ) = 1 виконується: f (a1 × a2 ) =			f (a1 )× f (a2 )
- функція			t(a)	визначення	кількості дільників		у	цілого числа
a = p α1	× p	2	α2 × ...× p	αk є функцією	мультиплікативною		і	обчислюється за
1				k

формулою:

t(a) = (1 + a1 )(1 + a2 )...(1 + ak )

-функція S (a) обчислення суми усіх дільників числа a = p1α1 × p2α2 × ...× pk αk є функцією мультиплікативною і обчислюється за формулою:

	S (a) =	p1α1 +1 -1	×	p2	α2 +1 -1	× ...×	pk αk +1 -1
		p1 -1		p2 -1			pk -1

-числа, для яких S (a) = 2a носять назву „ досконалих” чисел;

-числа (2k -1) можуть бути простими тільки, коли k - просте число, такі числа носять назву простих чисел Мерсенна;

- функція, яка обчислює кількість чисел, взаємопростих з даним цілим

a = p α1

× p

2

α2

× ...× p

αk

, менших за це число, називається функцією Ейлера j(a) і

1

k

також є функцією мультиплікативною.

j(a) = (p

α1 - p

α1 −1 )(p

α2

- p

α2 −1 )...(p

k

αk - p

αk −1 )

1

1

2

2

k

- кількість

чисел

взаємнопростих

з кожним із дільників числа

a = p α1

× p

2

α2

× ...× p

αk

дорівнює самому числу a

1

k

-кількість натуральних чисел mi , які не перевищують число a , ( mi £ a ), і мають з цим числом найбільший спільний дільник d , тобто (a ,mi ) = d , дорівнює

24

= ϕ a k d

Контрольні питання до теми №2.

19.Дати визначення функцій виділення цілої та дробової частин дійсного числа α , тобто [α] і {α}.

20.Записати функції [α] і {α} для чисел 25.45; 200; 34.98; -20.89; -145.04; 0.07; -0.07.

21.Яка кількість натуральних чисел таких, що діляться на 7, розташована на проміжках [1, 137]; [37, 396]?

22.Дати означення мультиплікативної функції. Навести приклади.

23.Дати означення функцій τ(a), S (a) .

24.Обчислити кількість і суму дільників для чисел 13, 81, 91, 100, 8712.

25.Дати означення недостатнього числа, надлишкового числа, досконалого числа. Навести приклади.

26.Які числа носять назву чисел Мерсенна?

27.Перевірити, чи є число 2096128 досконалим.

28.Дати означення функції Ейлера.

29.Обчислити функцію Ейлера для чисел з п.6.

30.Перевірити властивість 2 функції Ейлера для числа a = 6084 .

31.Скільки чисел в інтервалі від 1 до 120 не взаємно простих з числом 30.

25

ТЕМА №3 ПОРІВНЯННЯ (КОНГРУЕНЦІЇ). ВЛАСТИВОСТІ ПОРІВНЯНЬ

Питання 1. Основні поняття та теореми. Властивості конгруенцій. Питання 2. Повна та зведена системи лишків.

Питання 3. Повні та зведені системи лишків, як структури теорії груп. Мала теорема Ферма та теорема Ейлера.

Ключові терміни

Модуль ділення, конгруентні за модулем, конгруенція, рефлективність, симетричність, транзитивність, клас чисел за модулем m , лишок, найменший додатній лишок, абсолютно найменший лишок,повна система лишків, зведена система лишків, абелева група, напівгрупа, поле, кільце.

Питання 1. Основні поняття та теореми. Властивості конгруенцій.

Розглянемо ділення із залишком деяких цілих чисел на деяке певне ціле число m . Будемо називати число m модуль ділення цих чисел. Подання довільного цілого через неповну частку та залишок розглядалося в п. 1.1: a = m × q + r, 0 £ r < m . Серед множини цілих чисел, знайдуться такі, які діленням на модуль m дадуть різні неповні частки і

однаковий залишок.

Наприклад, якщо за модуль узяти m = 7 , то можна навести ряд чисел, які діленням на 7

дають залишок	1: 15 = 7 × 2 +1;	22 = 7 ×3 +1;	50 = 7 × 7 +1; 7778 = 7 ×1111+1
Числа, які від	ділення на	модуль m	дають рівні залишки r називаються рівно

залишкові, або конгруентні (порівняні) за модулем m .

Конгруенція чисел a і b за модулем m записується так:

a ≡ b(mod m)

Такі твердження є еквівалентними з конгруенцією a ≡ b(mod m):

1.a = mt + b, t Î Z - тобто a складає конгруенцію із своїм залишком від ділення на модуль.

2.m | a - b

Приклад:

Розглянувши попередній приклад, можемо записати:

15 ≡ 22 ≡ 50 ≡ 7778 ≡ 1(mod 7)

Ділення будь-якого натурального числа можна подати двічі, наприклад: 15 = 7 × 2 +1 , або 15 = 7 ×3 - 6 , що відповідає 2-м поданням через конгруенції:

15 ≡ 1(mod 7), 15 ≡ −6(mod 7) = 1 − 7(mod 7)

Отже у загальному випадку будь-яке число можна подати через конгруенцію так:

a ≡ b(mod m) або a ≡ b − m(mod m)

Поняття конгруенції можна подовжити на цілі від’ємні числа. Тобто b Î Z

Властивості конгруенцій:

∙ Для конгруенцій вірними є такі закони рівностей: o рефлективність – a ≡ a(mod m)

o симетричність – якщо a ≡ b(mod m), то b ≡ a(mod m)

26

o транзитивність – якщо a º b(mod m); b º c(mod m) , то a º c(mod m)

∙Інші властивості конгруенцій, які відповідають властивостям рівностей.

1.Конгруенції можна додавати:

a º b(mod m); c º d (mod m) a + c º b + d (mod m)

Дійсно, a = m × q1 + b, c = m × q2 + d . Додамо дві рівності:

a + c = m × (q1 + q2 )+ b + d , (q1 + q2 )Î Z , отже a + c º b + d (mod m)

Властивість розповсюджується на довільну кількість порівнянь.

2.Доданок з будь-якого боку конгруенції можна перенести у інший бік із зміною знаку:

a + b º c(mod m) a º c - b(mod m)

Дійсно, розглядаючи за законом рефлективності конгруенцію - b = -b(mod m), додамо її до вихідної a + b º c(mod m), отримаємо a º c - b(mod m)

3. Оскільки mt º 0(mod m), t Î Z , то до кожної з частин конгруенції можна додати будь-яке число, кратне модулю.

a º b(mod m) a + mt º b + mt(mod m)

4. Конгруенції можна множити:

a º b(mod m); c º d (mod m) a = mt + b; c = mq + d a × c = m2tq + mtd + mqb + bd

ac = m(mtq + qb + td ) + bd; mtq + qb + td = t1 Î Z ac = mt1 + bd ac º bd (mod m)

Властивість розповсюджується на довільну кількість порівнянь.

5.Обидві частини конгруенції можна піднести до одного степеня:

Якщо a º b(mod m) a n º bn (mod m)

6.Обидві частини конгруенції можна помножити на однакове число k . Вірним є k º k(mod m), отже за властивістю 5 маємо ka º kb(mod m)

7.Узагальнення: Якщо у поліномі від k змінних із сталими коефіцієнтами

S = ∑ Aα1 ,...,αk x1

α1 ...xk

αk

коефіцієнти Aα1 ,...,αk

замінити

на числа Bα1 ,...,αk ,

конгруені

Aα1 ,...,αk за модулем m і змінні xi

(i =

)

замінити на конгруентні їм за модулем

1, k

m змінні yi

(i =

), то новий вираз поліному S

буде конгруентним вихідному

1, k

поліному за модулем m .

α1 ...yk αk (mod m)

S = ∑ Aα1 ,...,αk x1

α1 ...xk αk

º ∑ Bα1 ,...,αk y1

Для доведення використовуються властивості 1-6.

Зокрема, для полінома n -го степеня від однієї змінної:

n

n

ai º bi (mod m),

xi º yi (mod m), (i =

) ∑ai xn−i º ∑bi y n−i (mod m)

0, n

i=0

i=0

8. Обидві частини конгруенції можна поділити на спільний дільник

d , якщо

(m, d ) =1 : a º b(mod m), d | a, d | b, (d , m) = 1

a

º

b

(mod m)

d

d

∙ Властивості, які належать тільки конгруенціям.

Обидві частини конгруенції і модуль можна помножити на одне й те саме число. a º b(mod m) (a = mt + b)× k ka = kmt + kb ka º kb(mod km)

1.Обидві частини конгруенції і модуль можна розділити на будь-який їх спільний множник d

27

a º b(mod m); a = a d; b = b d , m = m d (a d = m dt + b d )×						1	a º b (mod m )
1	1	1	1	1	1	d	1	1	1

2.Якщо a та b можуть бути конгруентними по декількох модулях m1 , m2 ,..., mn , то конгруенція a і b вірна і за модулем, рівним НСК m1 , m2 ,..., mn .

Оскільки a − b	ділиться	на кожний з		модулів m1 , m2 ,..., mn , то воно		повинно
ділитися	і	на	НСК	цих	модулів,	тобто
a - b º 0(mod M ) a º b(mod M ),			M = НСК(m1 , m2 ,..., mn ).
3. Якщо один з боків конгруенції і модуль діляться на деяке число, то і інший бік
ділиться на це число.			a º b(mod m), a = mt + b,		c | a , c | m c | b	(за 3-ю
властивістю подільності)

4. Якщо a º b(mod m) (a, m) = (b, m)

Питання 2. Повна та зведена системи лишків

1. Повна система лишків.

Усі числа, які мають однаковий залишок r від ділення на деякий модуль m створюють клас чисел за модулем m . Усі числа цього класу можна отримати з формули ділення числа із залишком a = m × q + r , якщо надавати неповній частці q усіх значень з множини цілих чисел.

k різним залишкам від ділення за модулем m k < m будуть відповідати k різних класів. Модуль m за залишки може мати числа 0, 1, 2,..., m − 1. Отже, кількість таких

класів за довільним цілим модулем m становить m .

Кожне число з певного класу носить назву лишок відносно усіх інших чисел класу.

Якщо q = 0 то лишок r є найменший додатній лишок.

Найменший лишок за абсолютною величиною називається абсолютно найменший лишок і позначається δ .

Приклад: Візьмемо за модуль число m = 7 . Тоді найменшими додатними лишками будуть числа 1, 2, 3, 4, 5, 6 . Для кожного з них можна записати клас чисел за модулем 7:

a1 = 7 × q1 +1 a1 º 1(mod 7),			a4	= 7 × q4	+ 4 a4	º 4(mod 7),
a2	= 7 × q2 + 2 a2	º 2(mod 7),	a5	= 7 × q5	+ 5 a5	º 5(mod 7),
a3	= 7 × q3 + 3 a3	º 3(mod 7)	a6	= 7 × q6	+ 6 a6	º 6(mod 7)

При цьому, створюючи відповідний клас i, (i = 1,6), неповна частка qi пробігає всю

множину цілих чисел.

Абсолютно найменшими лишками за модулем 7 будуть числа − 3, − 2, −1, 0, 1, 2, 3 Якщо порівняти їх з найменшими додатними лишками, можна помітити, що для лишків

r <	m	=	7	d = r , а для r >	m	=	7	d = r - m .
2		2		2		2

В такий спосіб будується множина абсолютно найменших лишків за будь-яким

модулем. Якщо модуль m є парним числом, то для r = m можна за абсолютно

2

найменший лишок брати або m , або - m .

2 2

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

28

Найменші додатні лишки 0, 1, ..., m −1						складають повну систему. Абсолютно найменші
	m −1		m −1			m			m
лишки -		,...,-1, 0, 1,...,			для m	непарного і -		-1 ,...,-1,0,1,...,		для m	парного
	2		2			2			2

теж складають повну систему лишків. Узагальнення:

1. Будь-які m чисел, які попарно не конгруентні за модулем m складають повну систему лишків за цим модулем.

2. Якщо (a, m) =1 і у виразі ax + b, b Z x пробігає усі значення повної системи лишків

за модулем m , то ax + b теж приймає усі значення повної системи лишків.

Приклад. Перевірити, чи складає сукупність чисел (9, 2,16, 20, 27, 39, 46, 85)повну систему

лишків за модулем 8.

Розв’язання: Повна система лишків за модулем 8, складена з найменших додатних лишків є (0, 1, 2, 3, 4, 5, 6, 7). Необхідно впевнитися, що дана сукупність чисел складає конгруенції за модулем 8 такі, які входять до повної системи.

9 ≡ 1mod(8), 2 ≡ 2 mod(8), 16 ≡ 0 mod(8), 20 ≡ 4 mod(8), 27 ≡ 3 mod(8), 39 ≡ 7 mod(8), 46 ≡ 6 mod(8),

85 º 5 mod(8),

Дана сукупність чисел конгруентна лишкам з повної системи, але розташованим у іншому порядку. Отже вихідна система є повною системою лишків.

2. Зведена система лишків.

Згідно із властивістю лишків числа одного і того ж класу лишків за модулем m мають з m однаковий НСД: a = m × q1 + r, b = m × q2 + r, (a, m) = (b, m). Серед множини класів лишків за певним модулем m розглянемо такі класи лишків, у яких (m × qi + r, m) = 1 ,

тобто класи , взаємно прості з модулем m . Якщо взяти з кожного такого класу по числу, то складеться зведена система лишків за модулем m . Зазвичай зведену систему лишків виділяють з найменшої додатної системи лишків, або з абсолютно найменшої системи лишків.

Оскільки кількість чисел від 0 до m взаємно простих з m визначається функцією Ейлера j(m) , то відповідно, і кількість чисел у зведеній системі, і кількість класів, що відповідають зведеній системі, визначаються функцією Ейлера

		1			1				1
	-			-				-			,
j(m) = m 1			1				×...× 1
		p1			p2				pk
де p1 , p2 , ..., pk			- прості числа з канонічного розкладання m .

Приклад:

1.m =130 = 2 ×5 ×13, j(130) = (2 -1)(5 -1)(13 -1) = 48 , отже зведена система лишків за модулем 130 складається з 48 чисел, взаємно простих з 130.

2.m = 16 = 24 , j(16) = 24 - 23 = 8 , отже зведена система лишків за модулем 16 складається з 8 чисел, взаємно простих з 16, ці числа такі: 1, 3, 5, 7, 9, 11, 13, 15 . Ці числа і складають зведену систему лишків для числа 16.

Узагальнення:

1. Будь-які j(m) чисел, попарно не порівняльні за модулем m та взаємно прості з модулем, створюють зведену систему лишків.

2. Якщо (a, m) =1 і x пробігає усі значення зведеної системи лишків за модулем m , то ax теж приймає усі значення повної системи лишків.

29

Питання 3. Повні та зведені системи лишків, як структури теорії груп. Мала теорема Ферма та теорема Ейлера.

Базові означення з теорії поля.

Як відомо з вищої алгебри абелева (комутативна) група це множина F , на якій визначена одна бінарна операція (·)з властивостями

а) замкненість: a,b F c F : a ∙ b = c а) комутативність: a,b F : a ∙ b = b ∙ a ,

б) асоціативність "a,b, c Î F : a · b · c = (b · a)· c = a · (b · c) ,

в) існування нейтрального елемента: a F e F : a ∙ e = e ∙ a = a ,

г) існування для кожного елемента a множини F оберненого елемента:

"a Î F $a−1 Î F : a · a−1 = e .

Напівгрупа відрізняється від групи тим, що не для кожного ненульового елемента множини існує обернений елемент.

Поле — множина, на якій визначені дві бінарні операції: адитивна («+» або «додавання») та мультиплікативна («*» або «множення») на таких засадах:

а) за адитивною операцією множина створює абелеву групу, б) за мультиплікативною операцією всі ненульові елементи множини створюють абелеву групу.

в) виконується дистрибутивний закон.

Кільце – відрізняється від поля тим, що за мультиплікативною операцією множина створює напівгрупу.

Повернемося до повної системи лишків за модулем m .

Розглянемо повну систему лишків (наприклад повну систему найменших додатних лишків) за модулем m , яка створює m попарно не конгруентних класів. Позначимо цю систему:

(r1, r2 ,..., rm ), 0 £ ri £ m -1, ri ¹ rj (mod m).

На такій системі, враховуючи усі вище наведені властивості, можна розглянути дві бінарні операції: додавання та множення.

Додавання (адитивна операція): Оскільки конгруенції можна додавати без зміни модуля, отже результат додавання лишків з різних класів повної системи буде належати до цієї самої системи.

Причому для додавання виконуються властивості:

1.	"i, j =			: ri + rj º rj + ri (mod m) - комутативність;
		1, m
2.	"i, j, k =				:ri	+ rj + rk º (rj + ri )+ rk º ri + (rj	+ rk )(mod m) - асоціативність;
			1, m
3.	"ri $ 0 + mt					(t Î Z ): ri + mt º ri (mod m) -	клас, що	є	нейтральним	елементом	по
додаванню;
4.	"ri $ (- ri + mt ) (t Î Z ): ri - ri + mt º 0(mod m) - клас,							що	є оберненим	елементом	по
додаванню.

Висновок: Повна система лишків створює абелеву групу за додаванням.

Множення (мультиплікативна операція): Оскільки конгруенції можна множити без зміни модуля, отже результат множення лишків з різних класів повної системи буде належати до повної системи лишків за тим самим модулем.

Причому для множення виконуються властивості: 1. "i, j = 1, m : ri × rj º rj × ri (mod m) - комутативність;

30