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

2. "i, j, k = 1, m : ri × rj × rk º ri × (rj × rk )º (ri × rj )× rk (mod m) - асоціативність;

3."i, j, k = 1, m : ri × (rj + rk )º ri × rj + ri × rk (mod m) - дистрибутивність для лівого множника;

4."i, j, k = 1, m : (rj + rk )× ri º ri × rj + ri × rk (mod m) - дистрибутивність для правого множника.

Висновок:

Повна система лишків створює комутативну напівгрупу за множенням Ніяких обмежень на значення модуля m при цьому не накладалося.

Отже повна система лишків за будь-яким модулем m з операціями додавання та множення створює кільце.

Для визначення повної системи лишків, як поля не вистачає доведення існування єдиного нейтрального елементу з множення – одиниці, та єдиного оберненого елементу з множення до будь-якого елементу з повної системи лишків, тобто елементу, для якого виконується рівність:

ri × x º 1(mod m)

У випадку, коли модуль – просте число p існування одиничного елементу відносно множення для повної системи лишків доводить мала теорема Ферма.

Мала теорема Ферма.

Розглядаються цілі додатні числа: довільне ціле a та просте число p . Якщо (a, p) = 1 , то завжди вірно:

p | a p - a

Якщо записати у термінах модульної арифметики, то теорема Ферма набуває вигляду:

a p - a º 0(mod p) ,

або, використовуючи властивості конгруенцій,

a p−1 º 1(mod p)

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

Теорема Ейлера (узагальнення малої теореми Ферма):

Для двох довільних цілих додатних чисел a та m > 1 , таких, що (a, m) = 1, вірно: aϕ(m ) º 1(mod m),

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

Якщо m = p - просте число, функція Ейлера буде j(p) = p -1 , а теорема Ейлера набуває вигляду a p−1 º 1(mod p), що відповідає малій теоремі Ферма. Тобто теорема Ейлера розповсюджує результат теореми Ферма на будь-який складний цілий модуль.

Висновки:

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

31

2. За складеним модулем m одиниця з множення існує тільки на класах зведеної системи лишків.

Приклади

1. Показати, що 120 + 220 + 320 + 520 + 620 + 720 + 920 +1020 º -3(mod 11) .

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

Модуль 11 – просте число. Всі числа, що входять до суми – 1, 2, 3, 5, 6, 7, 9, 10 – належать до повної системи найменших додатних лишків за модулем 11. Всі ці числа взаємно прості з модулем. Отже, використовуючи малу теорему Ферма для кожного з

цих чисел можна записати: a10 º 1(mod 11), aÎ[1,2,3,5,7,9,10]

За властивостями конгруенцій можна піднести до квадрату обидві частини останньої конгруенції, тобто a 20 º 1(mod 11) і замінити числа в вихідній сумі на

еквівалентні:

1 +1 +1 +1+1 +1 +1 +1 º 8(mod 11)

Далі, використовуючи той факт, що 11t є нейтральним елементом по додаванню (виконує роль 0), віднімемо від 8 цей нейтральний елемент:

8 -11 = -3 º -3(mod 11) - що і необхідно було показати.

2. Показати, що 117 + 317 + 517 + 917 +1117 +1317 º 0(mod 14).

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

Всі числа, що входять до суми є взаємно простими з модулем 14 і належать до повної системи найменших лишків. Степінь, до якого треба піднести всі числа, непарний – 17. Отже, можна використати той факт, що від’ ємна величина в цьому степені зберігає знак.

Змінимо елементи повної системи найменших додатних лишків на елементи

повної	системи	абсолютно	найменших	лишків:
13 º -1(mod 14); 11 º -3(mod 14), 9 º -5(mod 14 ))
Підставимо до вихідної конгруенції
117 + 317 + 517 - 517 - 317 -117 º 0(mod 14) - що і потрібно було показати.
3. Показати, що число 7312 -1 ділиться на 105.
Розв’язання.
Якщо 7312 -1 ділиться на 105, то 7312 º 1(mod 105)
105 –	складений модуль, 105 = 3 ×5 × 7 . З кожним із складових 73 є взаємно простим,

отже для кожного модуля можна застосувати малу теорему Ферма: якщо (a , p) = 1 a p−1 º 1(mod p)

Отже, 732 º 1(mod 3); 734 º 1(mod 5); 736 º 1(mod 7)

Піднесемо першу отриману конгруенцію до 6-го степеня (за властивостями), другу – до 3-го степеня, третю – до 2-го степеня. Отримаємо:

7312 º 1(mod 3); 7312 º 1(mod 5); 7312 º 1(mod 7)

Використовуючи властивість, за якою конгруенцію, що виконується за різними модулями можна розглядати як конгруенцію за модулем, що складає НСК цих модулів,

запишемо: 7312 º 1(mod 3 ×5 × 7), або 7312 º 1(mod 105), що і потрібно було показати.

4. Довести, що за умови (a ,12) = 1, (b,12) =1 число a96 - b96 завжди ділиться на 144.

Розв’язання

32

Якщо число взаємно просте з числом 12, то воно буде взаємно простим і з числом 144 = 122 . Отже для такого числа виконується теорема Ейлера: aj(m) º 1(mod m)

Функція Ейлера для числа 144 дає результат: j(144) = j(32 × 24 )= (24 - 23 )(32 - 3)= 8 ×6 = 48

Отже a 48 º 1(mod 144) і b48 º 1(mod 144)

Використовуючи властивості конгруенцій, піднесемо обидві конгруенції до квадрату: a96 º 1(mod 144); b96 º 1(mod 144).

За властивостями конгруенцій ми можемо відняти від першої конгруенції другу:

a96 - b96 º 0(mod 144)

Остання конгруенція і означає, що за умови (a ,12) = 1, (b,12) =1 число a96 - b96 завжди ділиться на 144.

5. Знайти останню цифру числа 232323 .

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

Знаходження останньої цифри числа еквівалентно знаходженню залишка від ділення числа на 10. Позначимо невідому останню цифру через

x : 232323 º x(mod 10)

23 = 2 ×10 + 3 - підставимо до конгруенції:

(2 ×10 + 3)2323 º x(mod 10)

Якщо 2 ×10 + 3 піднести до степеня 2323 за біномом Ньютона, то у кожному з доданків крім останнього будемо мати за множник 10 в степенях від 2323 до 1. Всі такі доданки конгруентні 0 за модулем 10. Отже, після піднесення до степеня лівої частини конгруенції, будемо мати :

32323 º x(mod 10);

(3,10) = 1 , причому 10 – складене число. Для цієї пари виконується теорема Ейлера: 3j(10) º 1(mod 10)

j(10) = j(2 × 5) = 1× 4 = 4 34 º 1(mod 10)

Знайдемо найменший залишок для степені 2323 за модулем 4:

2323 = 580 3 ; 2323 = 580 × 4 + 3 4 4

34×580+3 º x(mod 10); (34 )580 × 33 º x(mod 10)

Оскільки 34 º 1(mod 10) 1580 ×33 = 27 = 20 + 7 º 7(mod 10) x = 7

Отже Останньою цифрою у числа 232323 буде цифра 7.

6. Знайти число, складене з цифр трьох найменших розрядів числа 3798 .

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

Необхідно знайти цифри трьох найменших розрядів даного числа, тобто необхідно знайти залишок від ділення даного числа на 1000.

(3,1000) = 1 3j(1000) º 1(mod 1000); j(1000) = j(23 ×53 )= (8 - 4)(125 - 25) = 400

3400 º 1(mod 1000)

Піднесемо конгруенцію до квадрату:

3800 º 1(mod 1000) 3798 ×9 º 1(mod 1000);

За властивостями конгруенцій ми до будь-якого боку конгруенції можемо додавати ціле число, кратне модулю. Додамо праворуч -1000:

3798 ×9 º 1 -1000(mod 1000) 3798 ×9 º -999(mod 1000)

33

За властивостями конгруенцій можна ділити обидва боки конгруенції на число, взаємно просте з модулем. Поділимо на 9 (9,1000)=1:

3798 º -111(mod 1000) 3798 º -111 +1000(mod 1000) 3798 º 889(mod 1000)

Відповідь: три останні цифри числа 3798 будуть 8, 8, 9. Отже число, що складається з них – 889.

Для ствердження про існування та єдиності оберненого елементу з множення необхідно спочатку дослідити питання існування та єдиність розв’язку конгруенції з одним невідомим a × x º 1(mod m) . Саме цьому питанню і присвячений наступний розділ.

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

1числа, які від ділення на модуль m дають рівні залишки r називаються рівно залишковими, або конгруентними (порівнянними) за модулем m ;

2конгруенція розглядається на множині цілих чисел Z = 0,±1, ± 2, ± 3,... ;

3якщо a конгруентне b за модулем m , такі записи еквівалентні:

1. a º b(mod m),

2. a = b + m ×t , t Î Z , 3. m | (a - b);

4конгруенція рефлективна, транзитивна і симетрична;

5конгруенція двох цілих чисел за модулем m має 8 властивостей, що не змінюють модуль і 5 властивостей з урахуванням модуля. Використовуючи ці властивості конгруенції можна значно спрощувати.

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

цих класів є числа 0, 1, 2, ..., m -1. Кожний представник класу відносно інших представників цього класу носить назву ЛИШОК.

7

числа 0, 1, 2, ..., m -1 створюють повну систему найменших додатних лишків за

модулем m ;

m −1

m −1

m

m

-

,...,-1, 0, 1,...,

-

-1 ,...,-1,0,1,...,

8

найменші лишки

2

2

для m непарного і

2

2

для m парного складають повну систему абсолютно найменших лишків;

9

якщо (a, m) =1 і

у виразі

ax + b, b Z

x

пробігає усі значення

повної

системи

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

10

якщо серед повної системи лишків 0, 1, 2, ..., m −1 за складеним модулем m взяти

тільки ті класи, які є взаємно простими

з модулем m , то отримаємо

зведену

систему лишків за модулем m . Серед повної системи таких класів буде j(m) -

значення функції Ейлера для числа m ;

11

за малою теоремою Ферма для довільного цілого числа a і простого p за умови,

що (a , p) =1 число a p−1 від ділення на p завжди має у залишку число 1.

34

12 за теоремою Ейлера для довільного цілого числа a і довільного числа m такого, що (a ,m) = 1 число aϕ(m) від ділення на m завжди має у залишку число 1.

13 повна система лишків за довільним модулем m створює кільце.

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

1.Сформулюйте умову конгруентності двох чисел a і b .

2.Згадайте основні властивості конгруенцій.

3.Покажіть, що такі конгруенції не мають місця:

a )689 ≡ 13(mod 16); b )21138 ≡ 31(mod 49); c )8107 ≡ 7(mod 35)

4.В чому полягає умова, необхідна і достатня для того, щоб два числа a і b належали до одного класу за модулем m .

5.Дайте визначення лишку за певним модулем, найменшої додатної системи лишків, абсолютно найменшої системи лишків, зведеної системи лишків за певним модулем.

6.Із скількох елементів складається абсолютно найменша система лишків за модулем 13? Назвіть ці елементи.

7.Чи складає система лишків (6, 18, 39, 92, 155) повну систему лишків за модулем 5?

8.Із скількох елементів складається зведена система найменших додатних лишків за модулем 24? Назвіть ці елементи.

9.Сформулюйте малу теорему Ферма.

10.Сформулюйте теорему Ейлера.

11.Чи є комутативними операції додавання та множення в найменшій додатній системі лишків за певним модулем.

10.Яка величина є в найменшій додатній системі лишків за певним модулем є нейтральним елементом за додаванням. Чи існує єдиний обернений елемент за додаванням до кожного елементу найменшої додатної системи лишків за певним модулем?

12.Яка величина в найменшій додатній системі лишків за простим модулем є нейтральним елементом за множенням. Яка теорема присвячена цьому питанню?

13.Яку алгебраїчну структуру створює повна система лишків за певним модулем?

35

ТЕМА №4 КОНГРУЕНЦІЇ З ОДНИМ НЕВІДОМИМ.

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

a)Використання функції Ейлера ϕ(m) .

b)Використання властивостей конгруенцій.

c)Використання підходящих дробів для розв’язку конгруенцій.

d)Розв’язання конгруенцій типу 2k x ≡ b(mod m), (2, m) = (2, b) = 1

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

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

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

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

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

Алгебраїчна конгруенція з одним невідомим, степінь конгруенції, розв’язок конгруенції, конгруенції І-го степеня, поля Галуа, системи конгруенцій з одним невідомим, розв’ язок системи конгруенцій, китайська теорема про залишки, конгруенція n-го степеня, простий модуль, складений модуль, наслідок з теореми Ферма

Питання 1. Основні відомості.

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

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

Якщо an не ділиться на m , то n називається степінь конгруенції.

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

3.Дві конгруенції з одним невідомим називаються еквівалентними, якщо всякий розв'язок x однієї конгруенції є розв’язком іншої.

Теорема.

Якщо x = x1 задовольняє конгруенцію (1), то всяке число, яке належить до того самого класу лишків за модулем m , що й число x1 , також задовольняє цю конгруенцію, тобто розв'язок конгруенції складає весь клас чисел x ≡ x1 (mod m).

Доведення.

Це твердження безпосередньо випливає з властивостей конгруенцій. Справді, нехай x2 – будь-яке число, що належить до того самого класу лишків за модулемm , що й x1 ; тоді x2 ≡ x1 (mod m). За умовою x1 є розв'язок конгруенції (1), тобто має місце тотожна конгруенція f (x1 ) ≡ 0(mod m), , але тоді, згідно з властивістю конгруенцій (7),

матиме місце й конгруенція	f (x2 ) ≡ 0(mod m), , тобто x2 також буде розв'язком
конгруенції. Оскільки x2 —	будь-яке число класу x ≡ x1 (mod m), то весь цей клас

задовольнятиме дану конгруенцію.

Усі розв'язки конгруенції (1), що належать до одного класу чисел за модулем m , приймають за один розв'язок даної конгруенції. При цьому конгруенція (1) має стільки розв'язків, скільки класів чисел її задовольняють.

Приклад.

Розв’язати конгруенцію 141x5 − 126x3 + 196x2 − 111x + 36 ≡ 0(mod 7)

36

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

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

141 ≡ 1(mod 7), − 126 ≡ 0(mod 7), 196 ≡ 0 mod(7), −111 ≡ −6(mod 7) ≡ 1mod(7), 36 ≡ 1(mod 7)

Конгруенція прийме вигляд: x5 + x + 1 ≡ 0(mod 7)

Розв’язки будемо обирати з повної системи абсолютно найменших лишків за модулем 7:

(− 3, − 2, − 1, 0, 1, 2, 3)

Легко побачити, що 0,±1 не є коренями конгруенції. Перевіримо інші значення,

використавши схему Горнера кожний раз зводячи отримані числа до лишків за даним модулем з повної системи абсолютно найменших лишків:

		1		0			0		0			1			1
	2	1		2		4≡-3			8≡1				3		7≡0
	-2	1		0		4≡-3			0			3¹0
													(mod7)
	3	1		-2			-2		2			2¹0
													(mod7)
	-3	1		-1			0		1				0
	Із схеми Горнера видно, що конгруенція має два кореня з повної системи
абсолютно найменших лишків x1 = 2,						x2	= −3 . Отже розв’ язками даної конгруенції є два
класи:
	x1 = 7q + 2,		(x1 ≡ 2(mod 7)),			x2	= 7q − 3,		(x2 ≡ −3(mod 7))
	Якщо розглянути розв’язки у повній системі найменших додатних лишків, то
розв’язок буде такий: x1 = 7q + 2, (x1 ≡ 2(mod 7)),									x2	= 7q + 4, (x2				≡ 4(mod 7))

Теорема.

Якщо обидві частини конгруенції (1) помножити на ціле число k , взаємно просте з модулем m , то дістанемо конгруенцію, еквівалентну даній.

Доведення.

Припустимо, що x ≡ α(mod m) є деякий розв'язок конгруенції (1), тоді

f (α) ≡ 0(mod m)

Помножимо обидві частини цієї конгруенції на k , отримаємо: kf (α) ≡ 0(mod m) Отже, α є розв'язком і для конгруенції kf (x) ≡ 0(mod m)

В інший	бік: якщо α є розв'язком конгруенції kf (x) ≡ 0(mod m), тобто
kf (α) ≡ 0(mod m),	тоді обидві частини конгруенції можна скоротити на k , не змінюючи

модуля, бо (k, m) = 1, отже,

f (α) ≡ 0(mod m),

тобто α є розв'язком конгруенції (1), що і доводить наше твердження.

Зауважимо, що при розв'язуванні конгруенцій з невідомою величиною можна, не змінюючи модуля, скорочувати обидві частини конгруенції тільки на такий їх спільний дільник, який є взаємно простий з модулем (див. властивість 8, п.3.1).

37

Питання 2. Конгруенції першого степеня. Розв’ язання конгруенцій.

Конгруенції І-го степеня мають вигляд: ax + b ≡ 0(mod m) або ax ≡ b(mod m)

Дослідимо наявність розв’язків у такої конгруенції. По-перше розглянемо ситуацію, коли (a, m) = 1

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

Висновок.

За умови, що (a, m) = 1 конгруенція ax ≡ b(mod m) має єдиний розв’ язок.

По-друге розглянемо конгруенцію ax ≡ b(mod m) за умови (a, m) = d > 1

ax ≡ b(mod m) ax = b + mt . Отже, якщо d | a, d | m d | b , тоді складові конгруенції

можна подати так a = a1d , b = b1d , m = m1d , (a1, m1 ) = (b1 , m1 ) = 1, отже за властивістю конгруенцій таку конгруенцію можна скоротити на d . Отримаємо конгруенцію

a1 x ≡ b1 (mod m1 ).

З попереднього така конгруенція має єдиний розв’язок x ≡ x1 (mod m1 ) , або x = m1t + x1 . Але якщо розглянути повну систему лишків для модуля m = dm1 , то можна помітити, що у інтервал [0, m] попадають такі розв’язки:

x1 , x1 + m1 , x1 + 2m1 ,..., x1 + (d − 1)m1 , тобто кількість таких розв’язків - d . Ці розв’язки не конгруентні між собою за модулем m і в свою чергу кожний з них створює свій клас лишків.

Висновок.

За умови, що (a, m) = d > 1 конгруенція має хоча б один розв’ язок, якщо d | b . Цих

розв’язків є рівно d штук ( d класів). Перший з розв’язків знаходиться із скороченої на d конгруенції, інші обчислюються таким чином

x2 = x1 + m1 , x3 = x1 + 2 × m1 ,..., xd = x1 + (d -1)m1

Розв’ язання конгруенції першого порядку можна проводити різними методами. b. Використання функції Ейлера ϕ(m) .

Розглянемо конгруенцію ax ≡ b(mod m), (a, m) = 1 . За теоремою Ейлера в разі, якщо (a, m) = 1, aϕ(m ) ≡ 1(mod m), або, використовуючи рефлективність, 1 ≡ aϕ(m ) (mod m).

Перемножимо дві конгруенції: ax ≡ baϕ(m ) (mod m), або x ≡ baϕ(m )−1 (mod m).

Розв’язок знайдений. Але розв’язання за цим методом доволі часто буває нераціональним через необхідність підносити числа до значних степенів.

c. Використання властивостей конгруенцій. Приклади.

а) розв’язати конгруенцію: 15x ≡ 25(mod17)

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

По-перше, розглянемо НСД 15 та 17: (15,17) = 1, отже конгруенція має єдиний

розв’язок. Спростимо конгруенцію за властивостями: 25 і 15 мають спільний множник 5, який є взаємно простим з модулем 17. Отже, використовуючи властивості конгруенції,

38

можемо поділити конгруенцію на 5: 3x ≡ 5(mod17) Число 5 відповідає абсолютно найменшому лишку -12, який є кратний числу 3, отже 3x ≡ −12(mod17), скоротимо на 3: x ≡ −4(mod17). Отже конгруенція має єдиний розв’язок з повної системи абсолютно найменших лишків за модулем 17, або розв’язок з повної системи найменших додатних лишків: x = −4 + 17 = 13

б) Розв’язати конгруенцію: 5x ≡ 8125 − 629 (mod 7)

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

(5,7) = 1 - розв’язок 1. У конгруенції складові можна заміняти відповідними лишками з мінімальних систем – узагальнення властивостей конгруенції. Отже

8125 − 629 ≡ 1125 − (− 1)29 (mod 7), Вихідна конгруенція зміниться так:

5x ≡ 2(mod 7), − 2x ≡ 2(mod 7), . Відповідь: x ≡ −1(mod 7) або x ≡ 6(mod 7)

d. Використання підходящих дробів для розв’ язку конгруенцій.

Випадок ax ≡ b(mod m) , (a, m) = 1. Розкладемо у неперервний дріб відношення

m

= q +

1

.

q2 + ...

a

1`

+

1

qn

Будемо мати набір q1 , q2 ,..., qn . За відомою схемою побудуємо підходящі дроби

δi

=

Pi

. Розглянемо два останніх підходящих дроба: δn−1

=

Pn−1

, δn

=

Pn

=

m

.

Qn

Qi

Qn−1

a

З властивостей підходящих дробів відомо: PnQn−1 − Qn Pn−1 = (− 1)n , отже

mQn−1 − aPn−1 = (− 1)n . Враховуючи, що Qn−1 ціле число, можна mQn−1 вважати за модульний період, який можна відкинути. Тобто маємо aPn−1 = (− 1)n−1 mod(m). Помножимо ліву і праву частину на число (−1)n b :

a(− 1)n−1 bPn−1 ≡ b(mod m).

Отже, розв’язок конгруенції буде: x ≡ (− 1)n Pn−1b(mod m)

		Приклад.
		Розв’язати конгруенцію:							256x ≡ 179(mod 337)
		Розв’язання.
		(256,337) = 1 - розв’язок єдиний. Розкладемо відношення																					337			у неперервний дріб:
																				256
337		= 1 +	81	; q = 1;		256		= 3 +		13	; q			= 3;			81	= 6 +			3	; q			= 6;			13	= 4 +	1	; q			= 4;
													2											3									4
256			256	1		81			81							13				13							3		3
3	= 3; q5		= 3
1
		Будуємо схему:
				і		0			1					2		3									4				5
				qi					1					3		6									4				3
				Pi		1			1					4		25									104				337
				Qi		0			1					3		19									79				256

39

Із схеми маємо:

n = 5, P	= P = 104, b = 179 x = (-1)4	104 ×179(mod 337);		104 ×179	= 55 +	81
n−1	4		337			337

Отже, x º 81(mod 337)

e. Розв’ язання конгруенцій типу 2k x º b(mod m), (2, m) = (2, b) = 1

2k x = b + mt Обираючи t = 1 або t = −1 отримуємо b ± m º 0(mod 2s ). Чим більший степінь 2, ти краще. Нехай δ найбільший степінь 2, такий, що 2δ | b ± a . Якщо δ > k , маємо:

x = b ± m (mod m) 2k

Якщо δ < k , скорочуємо конгруенцію на 2δ та повторюємо процедуру для

еквівалентної конгруенції 2k −δ x = b ±δm (mod m) 2

Приклад:

Розв’язати конгруенцію: 256x º 179(mod 337)

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

256 = 28 , отже можна вихідну конгруенцію подати так:

28 x º 179(mod 337)

а)Обчислимо b + m = 179 + 337 = 516 = 22129 b + m º 0(mod 4)

b - m = 179 - 337 = -158 = -2 × 79 b - m º 0(mod 2)

Обираємо b + m = 516 . Найбільша степінь 2, яка ділить b + m є 2 < 8 , отже переходимо до еквівалентної конгруенції:

	б) 26 x º 129(mod 337)
129 + 337 = 466 = 2 × 233;					129 - 337 = -208 = -16 ×13 = -2413
	Обираємо b - m = -2413;				d = 4 < 6 , отже, еквівалентна конгруенція буде
	в) 22 x º -13(mod 337)
	b + m = -13 + 337 = 324 = 4 ×81 = 2281;					b - m = -350 = -2 ×175
	Обираємо b + m = 2281;				d = 2 = k = 2 , отже
x =	b + m	mod(m) =	2281	mod(337) = 81(mod 337)
22			22
	Відповідь:		x = 81(mod 337) - розв’язок співпадає з попереднім.

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

Отримавши правила для розв’язання конгруенцій з одним невідомим, можемо дати відповідь на питання:

ДЛЯ ЯКИХ ЕЛЕМЕНТІВ ПОВНОЇ СИСТЕМИ ЛИШКІВ ЗА ДОВІЛЬНИМ МОДУЛЕМ m ІСНУЄ ОБЕРНЕНИЙ ЕЛЕМЕНТ З МНОЖЕННЯ?

Щоб дати відповідь на це питання, треба розглянути розв’язання конгруенції ax º 1(mod m)

Виходячи з вимог існування розв’язку такої конгруенції – (a, m) = 1, бо права частина

конгруенції дорівнює 1. Якщо за a взяти елементи повної системи залишків (як базу для всіх класів чисел за модулем m ), то очевидно, що конгруенція не завжди буде мати розв’язок. Наприклад, m = 15, a = 5 . Отже, з повної системи треба відкинути всі елементи,

кратні модулю. Отримаємо зведену систему лишків, кількістю j(m) елементів. Для будь

40