Файл: Zastosuvannya_teoriyi_chisel_u_kriptografiyi_metodi.pdf

або

j(a) = (p1α1 - p1α1 −1 )(p2 α2 - p2 α2 −1 )...(pk αk - pk αk −1 ).

Приклади

ϕ (28 = 22 ×7) = ϕ (22 )ϕ (7) = (22 - 21 )(7 -1) = 2 ×6 = 12,

öå (1, 3, 5, 9,11,13,15,17,19, 23, 25, 27) ;

ϕ(101) = 100 оскільки 101 – просте число;

ϕ(10) = ϕ (2) ×ϕ (5) = (2 -1)(5 -1) = 4 ;

ϕ(100) = ϕ (22 ) ×ϕ (52 ) = (22 - 21 )(52 - 51 ) = 2 × 20 = 40 ;

ϕ(1024) = ϕ (210 ) = 210 - 29 = 1024 - 512 = 512 = 29 .

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

31

мультиплікативні функції:

1)кількість дільників τ (a);

2)суму дільників s(a);

3)функцію Ейлера ϕ(a).

32

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

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

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

3.3.Мала теорема Ферма і теорема Ейлера.

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

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

Розглянемо ділення з остачею довільних цілих чисел на деяке певне ціле число m . Будемо називати число m модулем ділення цих чисел. Подання довільного цілого через неповну частку та остачу розглядалося в п. 1.1. Таке подання єдине і має вигляд

a = m × q + r, 0 £ r < m .

33

Серед множини цілих чисел знайдуться такі, які діленням на

a≡ b(mod m):

1.a = mt + b, t Î Z – тобто a становить конгруенцію із

своєю остачею від ділення на модуль m .

2. m | a - b – якщо остача від ділення a на m дорівнює b , то m ділить без остачі a - b .

Приклад

Розглянувши попередній приклад, можемо записати: 15 ≡ 22 ≡ 50 ≡ 7778 ≡ 1(mod 7).

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

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

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

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

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

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

34

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

Для конгруенцій правильними є такі закони рівностей

b≡ a(mod m);

-транзитивність – якщо 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) .

Властивість поширюється на довільну кількість конгруенцій.

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

віншу частину із зміною знака:

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) ac ≡ bd (mod m).

Властивість поширюється на довільну кількість конгруенцій.

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

Якщо a ≡ b(mod m) an ≡ bn (mod m).

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

35