Файл: Zastosuvannya_teoriyi_chisel_u_kriptografiyi_metodi.pdf

число, що складається з них – 889.

7. Знайти остачу від ділення 623854 на 26.

Розв’язання

Позначимо остачу від ділення даного числа 623854 на 26 через x .

Тоді можна записати конгруенцію 623854 º x(mod 26). Оскільки модуль – парне число, 62 – парне число, степінь

парного числа – парне число, то й x теж повинно бути парним числом за властивостями конгруенцій. Отже, можна перепозначити x = 2 y і конгруенцію записати так:

313854 × 23854 º 2 y(mod13 × 2) .

За властивостями конгруенцій таку конгруенцію можна скоротити на 2:

313854 × 23853 º y (mod13) .

Отримали нову задачу – знайти остачу від ділення числа

степінь 3854 парний, відповідно

313854 × 23853 º (-8)3854 × 23853 (mod13) 83854 × 23853 º y (mod13)

(23 )3854 × 23853 º y (mod13) 211562 × 23853 º y (mod13)

211562+3853 = 215415 º y (mod13) .

Оскільки (2,13) = 1 , 13 – просте число, за теоремою Ферма

213−1 = 212 º 1(mod13)

З’ясуємо якою буде остача від ділення степені 15415 на 12:

15415 =12 ×1284 + 7

Отже, 215415 = 212×1284+7 = 212×1284 × 27 º 27 (mod13)

{

º1(mod13)

128 º11 º y (mod13) y º11(mod13) .

Що означає, що остача від ділення числа a = 313854 × 23853 на

46

13 буде дорівнювати 11.

Отже, остачею від ділення 623854 на 26 буде число x = 2 y = 22 .

ЗАВДАННЯ ДЛЯ ВИКОНАННЯ ІНДИВІДУАЛЬНИХ КОНТРОЛЬНИХ РОБІТ ЗА ТЕМОЮ 3

ЗАВДАННЯ 7

Знайдіть остачу від ділення

47

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

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

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

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

4.2. Обернений елемент за множенням.

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

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

Конгруенції І степеня, обернений елемент за модулем m , розв’язок конгруенції, системи конгруенцій з одним невідомим, розв’язок системи конгруенцій, китайська теорема про остачі.

4.1. КОНГРУЕНЦІЇ ПЕРШОГО СТЕПЕНЯ. РОЗВ’ЯЗАННЯ КОНГРУЕНЦІЙ

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

Розв’язком конгруенції І степеня за модулем m є клас чисел x1 + mt, t Z , кожний лишок якого за підстановки у конгруенцію приводить до тотожної конгруенції b ≡ b(mod m).

Як правило, x1 належить до повної системи найменших

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

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

48

Висновок

За умови, що (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 ).

Висновок

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

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

x2 = x1 + m1 ,..., xd = x1 + (d − 1)m1

49

РОЗВ’ЯЗАННЯ КОНГРУЕНЦІЇ ПЕРШОГО ПОРЯДКУ МОЖНА ПРОВОДИТИ РІЗНИМИ МЕТОДАМИ:

4.1.1 ВИКОРИСТАННЯ ВЛАСТИВОСТЕЙ КОНГРУЕНЦІЙ.

Приклади

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

Розв’язання

По-перше, розглянемо НСД 15 та 17: (15,17) = 1, отже

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

лишку -12, який є кратний числу 3, отже, 3x º -12(mod17) скоротимо на 3: x º -4(mod17). Таким чином, конгруенція має

єдиний розв’язок з повної системи абсолютно найменших лишків за модулем 17, або розв’язок з повної системи найменших додатних лишків: x = −4 + 17 = 13 .

б) Розв’язати конгруенцію 10x ≡ 35(mod 55).

Розв’язання

(10,55) = 5 > 1, 5 | 35 . Отже, ця конгруенція має 5 розв’язків. Скоротимо конгруенцію на d = 5 :

2x ≡ 7(mod11) - така конгруенція має єдиний розв’язок, оскільки (2,11) = 1

2x ≡ 7 + 11(mod11) 2x ≡ 18(mod11) x ≡ 9(mod11).

Конгруенція 10x ≡ 35(mod 55) буде мати 5 таких розв’язків:

x0 º 9 (mod 55) , x1 º 9 +11×1 =18(mod 55) ,

50