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

Приклад: Числа 6, 10, 15 – взаємно прості, бо (6,10,15) = 1 , але вони не попарно прості. Числа 7, 13, 23 – попарно прості, бо (7,13) = (7,23) = (13,23) = 1 , і одночасно вони взаємно прості.

НСД двох цілих чисел а і b.

1. Якщо b | a , то (a, b) = b і кількість дільників у чисел a та b співпадає з кількістю

дільників b .

2. Якщо a = bq + r , то кількість дільників a співпадає із кількістю спільних дільників b та r , зокрема

(a, b) = (b, r ) ( витікає з властивості 4. п.1.1).

3. Якщо a0 = cq0 + r0 , a1 = cq1 + r1 ,..., an = cqn + rn (a0 , a1 ,..., an , c) = (c, r0 , r1 ,...rn )

Алгоритм Евкліда для знаходження НСД двох чисел a і b .

Цей алгоритм ґрунтується на попередніх твердженнях. Розглянемо a та b , причому a ³ b . Тоді можна записати обмежений ланцюжок ділень з залишком:

Досліджуючи цей ланцюжок з останнього ділення уверх, отримаємо: rn | rn−1 rn | rn−2 (rn−2 , rn−1 ) = rn ;

rn | rn−2 rn | rn−3 (rn−3 , rn−2 ) = (rn−2 , rn−1 ) = rn ;

.......................................

Отже,

-сукупність дільників a та b співпадає з сукупністю дільників їх НСД.

-НСД a та b дорівнює останньому ненульовому залишку в ланцюжку ділень

за алгоритмом Евкліда. Узагальненням алгоритму Евкліду буде теорема:

Спільний дільник двох довільних цілих чисел d = (a,b) можна єдиним способом подати лінійною комбінацією цих чисел:

d = ax + by, x, y Î Z , x ¹ 0, y ¹ одночасно.

Доведення теореми витікає з алгоритму Евкліду, якщо всі залишки, починаючи з rn = d поступово виразити через попередні залишки, а потім і через a та b .

Приклад:

1. Знайти НСД a=648 та b=261. 2. Знайти x, y : d = ax + by .

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

1. Шукаємо НСД

6

2. Шукаємо подання НСД лінійною комбінацією:

d = r2 = b - r1q1 ; r1 = a - bq0 d = b - (a - bq0 )q1 = a(- q1 )+ b(1 + q0 q1 ) = -2a + (1+ 4)b = -2a + 5b

Отже x = −2, y = 5

Деякі властивості НСД:

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

3.Якщо (a, b) = 1 (ca, b) = (c, b);

4.Якщо (a, b) = 1. b | ac b | c ;

5.Якщо a1 , a2 ,..., am взаємно прості з кожним з b1 , b2 ,..., bn , то добуток a1 × a2 ×... × am взаємно простий з добутком b1 × b2 ×... × bn

7

Питання 3 Найменше спільне кратне (НСК).

Дані числа a1 , a2 ,..., am . Кожне з чисел, що є кратним кожному з даних чисел, носить

назву спільне кратне (СК). Найменше із усіх кратних називається найменше спільне кратне даних чисел.

Теореми:

1.Сукупність спільних кратних чисел a та b співпадає з сукупністю кратних для їх НСК.

2.НСК a та b дорівнює відношенню добутку цих чисел до їх НСД.

8

Питання 4 Прості числа. Єдиність розкладання довільного цілого числа на прості множники.

1. Вислови:

1.Число 1 має тільки один додатний дільник – самого себе. Одиниця стоїть осторонь у ряду натуральних чисел.

2.Найменший дільник, що не дорівнює 1, для будь-якого цілого числа є число

просте. (Візьмемо число a і його найменший дільник q ¹ 1 . Допускаємо, що q = q1 × r, q1 £ q, r £ q . Тоді a ділиться на q1 і на r , тобто a має дільник, менший за q , що є протиріччям вихідному посиланню.)

3. Найменший дільник, що не дорівнює 1, для будь-якого складеного цілого числа a

не перевищує значення a . (Нехай a = q × c . Оскільки q - найменший дільник, то c ³ q .

Отже ac ³ q 2 c, a ³ q 2 , або q £ a .

4.Простих чисел безкінечно багато.

5.Решето Ератосфена для вибору простих чисел, які не перевищують даного числа

N.

1)Обираємо перше просте число – p1 = 2 . Викреслюємо всі цілі числа з інтервалу (4, N ), кратні 2.

2)Обираємо наступне найменше просте число p2 = 3 . Викреслюємо всі цілі числа з інтервалу (9, N ), кратні 3.

3)Повторюємо процес з наступним p3 = 5 .

4)Обираючи чергове pk , звертаємо увагу на те, що кандидатів на викреслення

слід розглядати починаючи з числа pk 2 , бо всі менші складені числа викреслені, як такі, що кратні простим числам, меншим за pk .

5)Викреслення можна зупинити, коли pk перевищить N . Усі складені числа на той час будуть викреслені.

2.Єдиність розкладання довільного цілого числа на прості множники.

Базові вислови для складених чисел:

∙Довільне ціле a або взаємно просте з даним простим числом p < a , або ділиться на нього.

∙Якщо добуток декількох множників ділиться на просте число p , то хоча б один з множників теж ділиться на p .

∙Довільне ціле число можна розкласти на добуток простих множників єдиним способом. (враховуючи комутативність множення)

a= p1 × p2 ×... × pn

∙У наведеному розкладанні деякі з множників можуть повторюватися не

один раз. Позначивши через p1 , p2 ,..., pk тільки різні множники, а через a1 , a2 ,..., ak відповідні кратності входження множників до числа a ,

запишемо канонічне розкладання довільного цілого числа a на множники:

a = p1α1 × p2 α2 ×... × pk αk

9

∙У відповідності до вищенаведеної формули, кількість дільників τ довільного цілого числа a можна знайти так:

τ= (α1 +1)(α 2 +1)...(α k +1)

∙Розглянемо канонічне розкладання m довільних цілих чисел:

∙Сукупність спільних дільників декількох цілих чисел співпадає з кількістю дільників НСД цих чисел.

∙НСК декількох взаємно простих чисел дорівнює їх добутку, а сукупність кратних декількох чисел співпадає з сукупністю кратних НСК цих чисел.

Приклад:

Дані 2 числа 12348 та 867. Побудувати канонічну форму цих чисел, знайти їх НСД та НСК.

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

а) 12348 за ознаками ділення ділиться на 4(22) і на 9 (32)

12348 = 3087 × 22 = 22 × 32 × 343 = 22 × 32 × 73 - канонічне розкладання числа. Дільників у цього числа буде τ = (2 +1)(2 +1)(3 +1) = 36

б) 867 = 3 ×172 - канонічне розкладання другого числа. Дільників у другого числа буде

τ = (1+1)(2 +1) = 6 : 1, 3, 17, 289, 51 та 867

НСД - d = (12348,867) = 2min (2,0)3min (2,1)7 min (3,0)17min (0,2) = 3

НСК - m = 2max (2,0)3max (2,1)7max (3,0)17max (0,2) = 223273172 = 4235364

10