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

якого елементу зведеної системи за модулем m обернений елемент буде розв’язком конгруенції ax º 1(mod m) :

x º aϕ(m )−1 (mod m)

Позначимо обернений елемент через a−1 .

Отже для складеного модуля m обернений елемент існує тільки для його зведеної системи лишків і для будь якого елементу a з класу зведеної системи лишків дорівнює:

a−1 º aϕ(m )−1 (mod m)

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

Отже для будь якого елементу повної системи лишків за простим модулем p обернений елемент заданий та єдиний:

a−1 º a p−2 (mod p).

Висновки.

1. Повна система лишків за простим модулем p за операцією множення створює

абелеву групу.

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

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

Питання 4. Системи конгруенцій першого степеня з одним невідомим.

Розглянемо систему конгруенцій

a1 x º b1			(mod m1 ),	(a1 , m1 ) = 1,
a		x º b	(mod m ),	(a	, m ) = 1,
	2	2	2	2	2	(1)
	K K K K K K K
a		x º b (mod m ),		(a	, m ) = 1
	k	k	k	k	k

з одним невідомим за різними модулями. Будемо вважати також, що m1 , m2 ,..., mk -

попарно прості: (mi , m j )= 1, i = 1, k; j = 1, k; i ¹ j .

Розв’ язок системи конгруенцій з одним невідомим є таке ціле число α , яке задовольняє усі конгруенції даної системи.

По-перше, спростимо дану систему. Оскільки (ai , mi ) = 1, i = 1, k , то для ai існує обернений елемент ai −1 : ai × ai −1 º 1(mod mi ) . Помноживши кожне рівняння системи на свій зворотній елемент, перейдемо до системи, еквівалентної даній:

x º c1 (mod m1 ),

	2	2	),
x º c		(mod m
			(2)
K K K K
x º c		(mod m ),
	k	k

Отже, розв’язавши систему (1), ми тим самим знайдемо розв’язок системи (2). Відповідь про існування та структуру розв’ язку системи (2) дає

Китайська теорема про залишки:

41

Нехай дані k попарно простих чисел m1 , m2 ,..., mk та чисел c1, c2 ,..., ck , таких, що

0 £ ci £ mi

-1,

i =

. Тоді існує таке єдине ціле число α , у якого залишок від ділення на

1, k

mi становить ci (тобто a º ci (mod mi )).

Доведення.

Доводити будемо побудовою числа α . Позначимо через M НСК всіх модулів.

Оскільки вони попарно прості, то M = m1m2 ...mk . Далі побудуємо систему чисел

=

M

=

m1m2 ...mi ...mk

= m m

i =

M

i

...m

m

...m

,

1, k

mi

mi

1

2

i−1

i+1

k

Кожне M i

є взаємно простим з числом mi

, тому для нього існує обернений елемент

M

i

−1 º M

ϕ(mi )−1 mod(m )

i

i

k

−1ci

Побудуємо число: a = ∑ M i M i

i=1

Тоді розв’язком системи (2) буде клас лишків, що задовольняє конгруенції:

x º a(mod M )

Дійсно, підставимо α у першу конгруенцію системи (2):

M

1

M

1

−1c + M

2

M

−1c

2

+ ... + M

k

M

k

−1c

k

º c (mod m )

1

2

1

1

Всі доданки, починаючи з другого діляться на m1 , бо цей модуль присутній у M i , як

множник. Тому всі ці доданки конгруентні 0 за модулем m . Добуток M

M

−1

º 1(mod m ) за

1

1

1

1

побудовою,

(M1, m1 ) = 1 . Залишається тотожна конгруенція c1 º c1 (mod m1 ).

У другому рівнянні не конгруентним 0 за модулем m2

буде тільки доданок

M 2 M 2

−1c2 . Отже α є розв’язком для другої конгруенції і т. д.

Розв’язок підійде до кожної конгруенції в силу своєї структури.

Висновок: Розв’ язок системи (2) існує, і це є клас чисел

x = α + Mt,

t Z

Приклад. Розв’язати систему конгруенцій.

x º 16(mod13);x º 128(mod 5)x º 82(mod 3)x º 55(mod 7)

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

По-перше спростимо систему:

x º 3(mod13);
x º -2(mod 5)
x º 1(mod 3)
x º -1(mod	7)
M i : M1 = 5	× 3	× 7 = 105; M 2 = 13 × 3 × 7 = 273; M 3 = 13 × 5 × 7 = 455; M 4 = 13 × 5 × 3 = 195

Знайдемо обернені значення до M i ,	i = 1,2,3,4 :
105M1−1 º 1mod(13): 105 = 13 ×8 +1	273M 2		−1 º 1mod(5): 273 × 2 = 546 = 545 +1
105 º 1(mod13) M1−1 º 1(mod13)	M 2	−1 º 2 (mod 5)

42

455M 3	−1 º 1mod(3):		195M 4		−1 º 1mod(7): 195 × 6 = 1170 = 167 × 7 +1
455 × 2 = 910 = 909 +1 M 3		−1 º 2(mod 3)	M 4	−1 º 6 (mod 7) º -1(mod 7)

Будуємо розв’язок:

a = 105 ×1× 3 + 273 × 2 × (- 2)+ 455 × 2 ×1 +195 × (-1)× (-1) = 315 -1092 + 910 +195 = 328

Перевірка:

328 = 25 ×13 + 3; 328 = 65 × 5 + 3 = 66 × 5	- 2;
328 = 109 × 3 +1; 328 = 46 × 7 + 6 = 47 ×8	-1
Система розв’язана вірно.
Відповідь: розв’язком системи є клас лишків x = 328 + 13 × 5 × 3 × 7 × t								за модулем, що
дорівнює НСК 13, 5, 3, 7
Якщо у системі (1) для будь якої конгруенції ai x º bi (mod mi )						(ai , mi ) = d > 1, d | bi , то
		a	i		b				m
скорочуючи конгруенцію на d , переходимо до конгруенції				x º	i		mod			i	і вже цю
		d			d				d

конгруенцію підставляємо до системи. Якщо для нової системи збереглася попарна простота модулів, то вона має єдиний розв’язок, згідно з китайською теоремою про залишки. Але в цьому випадку i -та конгруенція має d розв’язків:

x º c + t		mi	(mod m ), t		=	0, (d -1), отже необхідно розглянути, відповідно, d систем, в
	j d
i			i	j

кожній з яких на i − му місці буде стояти відповідний розв’язок конгруенції.

Якщо модулі системи конгруенцій не є попарно простими, тобто (mi , m j )= d > 1 , то для розв’язання системи треба додатково досліджувати існування розв’язку. Якщо він є, то

							m1m2 ...mk
це буде розв’язок за модулем, рівним НСК модулів системи: x º a mod							(m , m ,..., m )
							1 2		k
Розглянемо для прикладу систему з двох конгруенцій. Будемо вважати, що її
можна звести до вигляду:
x º c1	(mod m1 )
x º c2	(mod m2 )
Нехай (m1 , m2 ) = d > 1,		′	′	′	′
		m1 = m1 × d	, m2 = m2 × d ,	(m1	, m2 ) = 1
Будемо розв’язувати систему методом підстановки. З першої конгруенції можна
записати:	′
x = c1 + m1dt .
Розв’язок повинен задовольняти і другу конгруенцію. Підставимо x у другу
конгруенцію:
′	′	′	′
c1 + m1dt º c2 (mod m2 d ),		m1dt º c2	- c1 (mod m2d )
Отже виникла умова:
Якщо d | c2 - c1 , то друга конгруенція розв’ язок має. В іншому випадку –										ні.
Нехай умова виконується. Тоді розглядаємо конгруенцію m¢t º						c2 - c1		(mod m¢ ).
					1		d		2

Розв’язком її буде конгруенція

t = c2 - c1 (m1¢)−1 (mod m¢2 ). d

Розв’язок можна подати так: t = c2 - c1 (m1¢)−1 + m2¢t1 . d

43

Підставимо значення t											у вираз для x :									= c + m′(c − c )(m′)		+ m		t =
x = c + m′dt = c + m′d							c2				− c1					(m′)	+ m′t						m2
																−1					−1
1		1	1		1						d					1		2 2		1 1 2 1 1		1	d	2
= c + m′(m′)−1			(c	2	− c ) +				m1m2					t		2
1	1	1			1						d
Позначимо c + m′(m′)−1										(c		2	− c ) = x ,					m1m2		= M .
			1		1	1										1	1	d

Тоді розв’язок системи буде мати вигляд:

x ≡ x1 (mod M )

Висновки.

	x ≡ c1	(mod m1 )
1.Система з двох рівнянь виду	x ≡ c2	(mod m2 ) в разі (m1 , m2 ) = d > 1	буде мати

розв’язок тільки за умови, що d | c2 − c1 . В іншому разі система не сумісна. Якщо умова виконана і розв’язок є, він буде знайдений за модулем, який дорівнює НСК m1 та m2

2. Якщо система складається з k > 2 конгруенцій з модулями, що мають НСД>1, то перевірку необхідно проводити поступово. В разі, коли хоча б одна з отриманих конгруенцій в ході розв’язку немає розв’язку, то і вся система не сумісна. Якщо розв’язок є, то це буде конгруенція по НСК усіх модулів.

Питання 5 Конгруенції n-го степеня за простим модулем. Кількість коренів конгруенції n -го степеня за простим модулем

Розглянемо загальні теореми, які стосуються конгруенцій n-го степеня за простим модулем p . Припустимо, що задано конгруенцію

f (x) ≡ 0(mod p),

f (x) = a

xn + a xn−1

+ ... + a

n−1

x + a

n

,

(1)

0

1

де p - просте число і a0

не ділиться на p .

Теорема 1. Конгруенцію (1) завжди можна замінити на еквівалентну їй

f (x) ≡ 0(mod p), f (x) = xn + b xn−1 + ... + b

x + b

1

n−1

n

Справді,

через те що p —

просте і a0

не ділиться на

p завжди існує єдине число,

обернене до a0 : a0 a0

−1 ≡ 1(mod p),

a0

−1 ≡ a0 p−2 (mod p) . Помноживши конгруенцію (1) на a0

−1 ,

отримаємо еквівалентну конгруенцію із старшим коефіцієнтом b0 ≡ 1(mod p)

Теорема 2. Якщо степінь конгруенції (1) не менший від модуля конгруенції, то вона еквівалентна деякій конгруенції степеня, не вище за p − 1 (за тим самим модулем). Тобто,

якщо у (1)

n ³ p , то

≡ 0(mod p)

a xn + a xn−1

+ ... + a

n−1

x + a

n

≡ b x p−1

+ b x p− 2

+ ... + b

p− 2

x + b

p−1

0

1

0

1

Доведення.

Поділимо

f (x) на x p − x . Частку від ділення позначимо черезQ(x) , залишок – через

R(x). Тоді на підставі алгоритму ділення з остачею дістанемо:

f (x) = (x p − x)Q(x) + R(x)
де Q(x) –	поліном, степеня n − p ,	R(x) – поліном степеня,	не	більшого за p − 1 .
Коефіцієнти	Q(x) , R(x) – цілі числа.	За теоремою Ферма якщо	p	– просте число, то

x p − x ≡ 0(mod p) для будь-якого цілого х. Отже, отримаємо еквівалентну конгруенцію:

f (x) ≡ R(x)(mod p)

Висновок: Конгруенції f (x) ≡ 0(mod p) та R(x) ≡ 0(mod p) мають однакові корені.

44

Частинні випадки:

1.	(x p − x)| f (x) . Тоді R(x) ≡ 0(mod p) - тотожна, 0 ≡ 0(mod p), тобто вірна для будь
якого x .	R(x) ≡ bp−1 (mod p) - поліном нульового степеня. Якщо bp−1 не ділиться на p , то дана
2.

конгруенція не має розв’язків, бо вона зводиться до невірної конгруенції : bp−1 ≡ 0(mod p). Приклад. Знайти конгруенцію степені не вище 4, еквівалентну даній:

f (x) = x17 + 2x11 + 3x8 − 4x7 + 2x − 3 ≡ 0(mod 5)

Розв’язання: Поділимо f (x) на x5 − x . Для полегшення ділення використаємо наслідок з малої теореми Ферма ( a p−1 ≡ 1(mod p), (a, p) = 1 ).

Наслідок з теореми Ферма:

Якщо (a, p) = 1, n ≡ m(mod p − 1) an ≡ am (mod p).

Дійсно, нехай n > m, n = m + q(p − 1), За теоремою Ферма a p−1 ≡ 1(mod p). Піднесемо цю конгруенцію до степені q : a( p−1)q ≡ 1(mod p). Помножимо отриману конгруенцію і конгруенцію am ≡ am (mod p), дістанемо:

a( p−1)q+m ≡ am (mod p) , або an ≡ am (mod p)

За допомогою цього слідства можна зменшити степені вихідного полінома, взявши замість даних степенів їх залишки за модулем 4:

17 ≡ 1(mod 4); 11 ≡ 3(mod 4); 8 ≡ 0(mod 4); 7 ≡ 3(mod 4)

Отримаємо:

R(x) = x1 + 2x3 + 3x0 − 4x3 + 2x − 3 ≡ 0(mod 5) , або − 2x3 + 3x ≡ 0 mod(5),

або, замінивши лишок -2 на лишок 3(mod5), отримаємо: 3x3 + 3x ≡ 0 mod(5), і остаточно:

x3 + x ≡ 0 mod(5)

Очевидні розв'язки останньої конгруенції x1 ≡ 2(mod 5), x2 ≡ 3(mod 5)											будуть також і
розв'язками вихідної конгруенції.
Теорема 3. Якщо α1 —			деякий розв'язок конгруенції n − го степеня								f (x) ≡ 0(mod p),
то має місце тотожна конгруенція:
f (x) ≡ (x − α1 ) f1 (x)(mod p)											(2)
де f1 (x) — поліном		n − 1 -го	степеня. Старший коефіцієнт						полінома f1 (x) збігається з
старшим коефіцієнтом вихідного полінома					f (x) .
Доведення.		на x − α1
Поділимо f (x)			і частку позначимо через					f1 (x), остачу –		через R(x):
(x − α1 ) f1 (x) + R(x) ≡ 0(mod p).
За теоремою Безу R(x) = f (α1 ), але оскільки α1							—	розв'язок конгруенції, то
f (α1 ) ≡ 0(mod p) , отже справедливою буде конгруенція:
(x − α1 ) f1 (x) ≡ 0(mod p).				f (x) ділиться на			x − α1 за модулем
За таких умов кажуть,			що							p . Очевидно, що й
навпаки: якщо	f (x)	ділиться на		x − α1	з	нульовим		залишком за		модулем p (тобто
R(x) ≡ 0 mod(p) ),	то,	використовуючи			теорему		Безу,		можна	стверджувати, що
f (α1 ) = R(x) ≡ 0(mod p), звідки витікає, що α1 —						розв'язок конгруенції.

45

Висновок.		Конгруенція (1)		має за корінь x = a1				тоді і тільки тоді,		коли x - a1
ділить f (x) за модулем p .
Зауважимо, що теорема 3 і висновок з неї справедливі і для складеного модуля m .
Теорема 4.		Якщо	a1 , a2 ,..., ak ; (k £ n)			є різні корені конгруенції (1),			то її можна
подати у вигляді:
f (x) = (x - a1 )(x - a2 )...(x - ak ) fk (x) º 0 mod(p)										(3)
де	fk (x) - такий поліном степеня не вище n − k ,						що немає коренів за модулем p ,
старші коефіцієнти у f (x) та fk (x) співпадають.
Доведення.		f1 (x) з (2). Нехай a2 - деякий його корінь. Тоді f1 (x) можна подати за
Розглянемо
формулою (2):
f1 (x) º (x - a2 ) f2 (x)(mod p),
де	f2 (x) - поліном степеня не вищого за n − 2 .
Підставимо		f1 (x) у (2). Отримаємо
f (x) = (x - a1 )(x - a2 ) f2 (x) º 0 mod(p).
Якщо a2 = a1 , то корінь a1 - кратний.
У інший бік:			таке число, що (α 2			− α1 ) f1 (α 2 ) ≡ 0(mod p ).
Розглянемо a2 ¹ a1
Добуток двох або декількох чисел ділиться на просте число								p тоді і тільки тоді, коли на p
ділиться принаймні один з множників добутку. За умовою a1 та a2 не співпадають
a1 ¹ a2 (mod p).
Отже, (a2 - a1 ) не ділиться на p , і значить на p ділиться							f1 (x):
f1 (a2 ) º 0(mod p),						f1 (x) º 0(mod p) і для нього вірне подання
останнє означає, що a2 —			корінь конгруенції
(x - a2 ) f2 (x) º 0(mod p) .
Підставимо останній вираз до (2) (x - a1 )(x - a2 ) f2 (x) º 0(mod p)
Так поступово можна прийти до поліному fk (x), k £ n , який не має коренів за даним
модулем.	Якщо	конгруенція (1)		має	n	коренів,	то	fk (x) = f0 (x) = a0	-	старшому
коефіцієнтові конгруенції (1).
Висновок.		Якщо конгруенція (1)			n -го степеня за простим модулем					p (можна

вважати n ≤ p ) має n різних розв'язків a1 , a2 ,..., an то поліном			f (x) можна розкласти на n
лінійних множників типу (x - ai ), i =		та множник a0 :
	1, n
f (x) = a0 (x - a1 )(x - a2 )...(x - an ) º 0(mod p)			(4)

Приклад.

Розкласти конгруенцію за даним модулем: x4 + x3 - x2 + x - 2 º 0(mod 5)

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

По-перше, можна понизити степінь конгруенції, бо відносно степені конгруенції за наслідком теореми Ферма можна записати: 4 º 0(mod(5 -1)). Отже отримаємо еквівалентну конгруенцію:

x3 - x2 + x -1 º 0(mod 5)

46

Знайдемо корені еквівалентної конгруенції з повної системи абсолютно найменших лишків (- 2,-1,0,1,2). Підстановкою з’ясовуємо, що коренями конгруенції будуть x ≡ −2,1,2 .

Очевидно, що ці корені є коренями й вихідної конгруенції.

Застосуємо для розкладання вихідного поліному за модулем 5 схему Горнера:

	1	1	-1	1	-2
-2	1	-1	1	-1	0
1	1	0	1	0
2	1	2	0

З останнього рядка отримаємо конгруенцію першого степеня x + 2 º 0(mod 5). Розв’язок її - x º -2(mod 5) , співпадає з першим коренем. Отже, маємо для вихідного полінома однократні корені x1 º 1(mod 5), x2 º 1(mod 5) і корінь кратності 2 x3,4 º -2(mod 5).

Вихідна конгруенція розкладеться так:

(x + 2)2 (x -1)(x - 2) º 0(mod 5)

Теорема 5. Конгруенція n -го степеня за простим модулем не може мати більше ніж n різних розв'язків.

Доведення.

Нехай β – деякий розв'язок, відмінний від a1 , a2 ,..., an , тобто

b ¹ ai (mod p), i = 1, n ;

Підставимо в (4) β замість x :

a0 (b - a1 )(b - a2 )...(b - an ) º 0(mod p)

(4*)

Оскільки модуль простий, значить хоча б один з множників повинен ділитися на модуль p . Лінійні множники не діляться на модуль за допущенням доведення. Старший коефіцієнт конгруенції теж не ділиться на модуль, бо інакше степінь конгруенції був би нижчим. Отже приходимо до висновку, що конгруенція (4*) не можлива. Отже β не може бути коренем і не співпадати хоча б з одним значенням з набору a1 , a2 ,..., an .

Слід зауважити, що по-перше, ця теорема не підтверджує, взагалі, наявності

розв'язків конгруенції n -го степеня за простим модулем			p і, по-друге, для складених
модулів вона несправедлива, наприклад, у конгруенції першого степеня
16x º 32(mod 48) НСД (a, m) = (16,48) = 16,		16 | 32, . Отже,		конгруенція має шістнадцять
розв'язків.
Висновок.
Конгруенція f (x) º 0(mod p), f (x) = a	xn + a xn−1 + ... + a		n−1	x + a	n
0		1

має більше ніж n розв'язків тоді і тільки тоді, коли вона тотожна, тобто коли всі її коефіцієнти діляться на p .

Дійсно, якщо коефіцієнти даної конгруенції діляться на p , то конгруенція виконується за будь-якого значення x , тобто вона тотожна, число її розв'язків (що дорівнює p ) буде більше ніж n .

Питання 6 Конгруенції n-го степеня за складеним модулем.

Розглянемо конгруенцію

f (x) º 0(mod m),	f (x) = a	xn	+ a xn−1	+ ... + a	n−1	x + a			,	(1)
	0		1					n
Якщо в конгруенції (1)
m = m1m2 ×... × mk ,	(mi , m j ) = 1		"i ¹ j i, j =				,
					1, k

47

то конгруенція рівносильна системі:

f (x) º 0(mod m1 );
f (x) º 0(mod m2 );
	L
f (x) º 0(mod m );
	k

Якщо позначити через Ti кількість розв’язків i − ї конгруенції системи, то загальна кількість розв’язків вихідної конгруенції дорівнює:

T = T1 ×T2 ×... ×Tk

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

Схему розв’язання конгруенцій n -го степеня за модулем, чкий є добутком простих чисел, розглянемо на прикладі.

Приклад.

Розв’язати конгруенцію: x4 + 2x3 + 8x + 9 º 0(mod 35)

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

35 = 5 × 7 , отже дана конгруенція відповідає системі:

	4	+ 2x	3	+ 8x + 9	º 0(mod 5)
x
x4		+ 2x3 + 8x + 9 º 0(mod 7)

Після спрощення система буде мати вигляд:

	0	+ 2x	3	+ 3x -1 º 0(mod 5)
x
x4 + 2x3 + x + 2 º 0(mod 7)
Перша конгруенція:					2x2 + 3 º 0(mod 5); 2x2 - 2 º 0(mod 5);	x2 º 1(mod 5);
Розв’язки: x1 º1(mod 5); x2 º 4(mod 5)
Друга			конгруенція:		x4 + 2x3 + x + 2 º 0(mod 7). Шукаємо	розв’язки серед повної

системи абсолютно найменших лишків (- 3,-2,-1,0,1,2,3): 0, 1 – не розв’язки, x1 º -1(mod 7) – розв’язок. Інші розв’язки шукаємо за схемою Горнера. Знайдемо ще два -

x2 º -2(mod 7), x3 º 3(mod 7).

Отже маємо 2 розв’ язки у першій конгруенції і 3 розв’язки у другій. Загалом система, а отже і вихідна конгруенція має T = 2 × 3 = 6 розв’язків. Для того, щоб їх знайти необхідно розглянути 6 систем виду:

x º b1 (mod 5)			b1 Î (1,4)
x º b		(mod 7)	b Î (- 2,-1,3),
	2		2

Але ми можемо розв’ язати дану систему у загальному вигляді і маючи її загальний розв’язок, підставити потрібні значення b1 , b2 :

x º b1 (mod 5) x = b1 + 5t					(*)
Підставимо x у друге рівняння системи:
b + 5t º b (mod 7) 5t º b			- b (mod 7);	5−1 º 3(mod 7) t º 3(b	- b )(mod 7).
1	2	2	1	2	1
Отже t = 3(b2 - b1 ) + 7t1
Підставимо t		до (*): x = b1 + 5(3(b2 - b1 )+ 7t1 ) = b1 +15b2 -15b1 + 35t2 = -14b1 +15b2 + 35t1 ,

або

x º 21b1 +15b2 (mod 35) - загальна формула розв’язку.

Залишилось тільки по черзі підставити у неї значення b1 = (1,4), b2 = (- 2,-1,3)

48

Отже x º 26,6,31,19,34,24(mod 35)

Тепер розглянемо конгруенцію (1) в разі, якщо m = p1α1 × p2 α2 ×... × pk αk :

f (x) º 0(mod p α1	× p	α2	×... × p	αk )	(2)
1		2		k

Розв’язання такої конгруенції зводиться до розв’язання конгруенцій виду

f (x) º 0(mod pα )

(3)

Розв’язання останньої конгруенції зводиться до розв’язання конгруенції

f (x) º 0(mod p)

Для доведення цього факту нам необхідно буде згадати ряд Тейлора для розкладання полінома у околі точки x0 :

f

¢(x

)

f

¢¢(x

0

)

2

f (n ) (x

0

)

n

f (x) = f (x )

+

0

(x - x ) +

(x - x

0

)

+ ... +

(x

- x

0

) .

0

1!

0

2!

n!

Розглянемо конгруенцію (3), її розв’язок x º x1 (mod p), що еквівалентно запису

x = x1 + pt1,

t Î Z .

(**)

Підставимо це значення у конгруенцію

f (x) º 0(mod p2 ),

і розкладемо

f (x)

у ряд Тейлора у околі точки x1 :

f ¢(x

)

f ¢¢(x

)

2

f

(n) (x )

n

f (x + pt ) = f (x ) +

1

(x

+ pt - x

) +

1

(x

+ pt - x )

+ ... +

1

(x + pt - x

) ,

1

1

1

1!

1

1

1

2!

1

1

1

n!

1

1

1

або

f ¢(x1 )

f ¢¢(x1 )

f (n ) (x1 )

º 0(mod p2 )

f (x + pt ) = f (x )+

pt

+

p2t

2

+ ... +

pnt n

1

1

1

1!

1

2!

1

n!

1

Відпросимо усі складові, кратні

p2 :

f (x ) + f ¢(x )pt

º 0(mod p2 )

1

1

1

f (x), отже конгруенцію можна скоротити:

Оскільки x1 є розв’язком (3), то p |

f (x1 )

+ f ¢(x )t

º 0(mod p), або

f ¢(x )t º -

f (x1 )

(mod p). (Візьмемо випадок, коли

f ′(x )

p

1

1

1

1

p

1

не ділиться на

p .)

t1 º u1 (mod p).

Знайдемо

розв’язок

цієї

конгруенції,

позначимо

його

-

Отже

t1 = u1 + pt2 . Підставимо значення t

у (**):

x = x + p(u

+ pt

2

) = x + pu + p2t

2

,

t

2

Î Z .

Якщо позначити

x + pu

= x

2

,

то

будемо

1

1

1

1

1

1

мати:

x º x2 (mod p2 ), або x º x2 + p2t2

(***)

Підставляємо його у конгруенцію

f (x) º 0(mod p3 ),

Розкладаємо за рядом Тейлора в околі x2 , відкидаємо всі складові, кратні p3 :

f (x2 ) + f ¢(x2 )p2t2 º 0(mod p3 )

Зауважимо, що оскільки x1 º x2 (mod p) f ′(x1 ) º f ′(x2 )(mod p) f ′(x2 ) не ділиться на p2 , а f (x2 ) - ділиться. Скоротимо конгруенцію на p2 . Будемо мати:

f (x22 ) + f ¢(x2 )t2 º 0(mod p). Розв’язок t2 = u2 + pt3 підставимо до (***) p

x = x2 + p2 (u2 + pt3 ) = (x2 + p2u2 )+ p3t3 , x2 + p2u2 = x3 x º x3 (mod p3 )

Продовжуючи таким чином, знайдемо кінець кінцем конгруенцію x º xα (mod pα ), яка є розв’язком конгруенції (3).

49

Висновок: Будь який розв’язок x º x1 (mod p) конгруенції

f (x) º 0(mod p) за умови,

що f ′(x1 ) не ділиться на p , дає єдиний розв’язок конгруенції (3).

Приклад.

Розв’язати конгруенцію x4 + 7x + 4 º 0(mod 27)

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

Маємо x4 + 7x + 4 º 0(mod 33 ). Отже спочатку шукаємо розв’язок конгруенції

x4 + 7x + 4 º 0(mod 3).

По-перше, спростимо її: x0 + x +1 º 0(mod 3), або x º -2(mod 3) . Маємо розв’ язок:

x º 1(mod 3),

x = 1 + 3t . Підставимо цей x у конгруенцію x4 + 7x + 4 º 0(mod 9) .

1

f ¢(x) = 4x3 + 7;

f ¢(1) = 11 º 2(mod 9) - не ділиться на

f (1) = 14 + 7 + 4 = 12 º 3(mod 9);

p = 3

′

×3t1 º 0(mod 9). Поділимо конгруенцію на p = 3 :

f (1)+ f (1)

f (1)

+ f ¢(1)t

º 0(mod 3) 1 + 2t

º 0(mod 3), 2t

º -1(mod 3); t

º 1(mod 3); t = 1 + 3t

.

2

3

1

1

1

1

1

x : x = 1 + 3t1 = 1 + 3(1 + 3t2 ) = 4 + 9t2 .

Підставимо

значення t1 у формулу для

Отже

знайшли розв’язок x º 4(mod 9).

x = 4 + 9t2

підставимо до конгруенції x4 + 7x + 4 º 0(mod 27).

f (4) = 256 + 7 × 4 + 4 = 288 º 18(mod 27); f ¢(x) = 4x3 + 7;

f ¢(4) = 4 × 43 + 7 = 263 º 20(mod 27)

′

9t2 º 0(mod 27). Поділимо конгруенцію на

p

2

= 9 :

f (4) + f (4)×

f (4)

+ f ¢(4)t

2 º 0(mod 3) 2 + 20t2 º 0(mod 3),

2t2 º -2(mod 3); t2

º -1(mod 3); t2

= 2 + 3t3 .

9

x = 4 + 9t2 = 4 + 9(2 + 3t3 ) = 22 + 27t3 x º 22(mod 27)

Отже розв’язком конгруенції x4 + 7x + 4 º 0(mod 27)

буде

клас чисел

x = 22 + 27t .

Розв’язок єдиний.

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

–Алгебраїчною конгруенцією з одним невідомим називається конгруенція виду:

f (x) ≡ 0(mod m), m Z , f (x) = a	n	x n + a	n−1	x n−1 + ... + a x + a	0	;
				1

–розв’язати конгруенцію означає знайти усі такі xi , які задовольняють конгруенцію;

–дві конгруенції з одним невідомим називаються еквівалентними, якщо всякий

розв'язок x однієї конгруенції є розв’язком іншої.

–за один розв’язок конгруенції приймається весь клас лишків, до яких належить x .

–конгруенція має стільки розв’язків, скільки класів її задовольняють;

–конгруенція 1-го степеня має вигляд ax º b(mod m)

–	конгруенція 1-го степеня ax º b(mod m) має єдиний розв’ язок в разі, якщо (a ,m) = 1
–	за умови, що (a ,m) = d > 1 конгруенція має розв’язок, якщо d | b . Цих розв’язків є
	рівно d штук ( d класів). Перший з розв’язків знаходиться із скороченої на d
	конгруенції, інші обчислюються, як x2 = x1 + m1 ,..., xd = x1 + (d -1)m1

–якщо у конгруенції ax º b(mod m) (a ,m) = d > 1 і d не ділить b , то така конгруенція розв’язку немає;

–найвідомішими методами розв’язання конгруенцій 1-го порядку є: за властивостями, за допомогою оберненого елементу, якщо він існує, за допомогою неперервних дробів;

50