Файл: Теорія чисел в криптографії.pdf

151 = [11,1,1,1,1,2] 13

Наведена схема має вигляд:

Тобто дріб 151 має такі підходящі дроби:

проаналізувати таблицю, то можна помітити, що дане число розташовано між двома сусідніми підходящими дробами.

Приклад.

Маємо неперервний дріб [2,1,3,4,1,2].

Побудувати відповідне найменше раціональне число a . b

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

Будуємо таблицю для обчислення підходящих дробів і згідно схеми обчислюємо всі підходящі дроби.

16

даний в умові задачі неперервний дріб.

Висновки.

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

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

інші цілі числа - складені; - простих чисел безкінечно багато;

- якщо пара цілих чисел a та b має спільні дільники, то серед них обов’язково є найбільший спільний дільник (НСД) d = (a ,b);

- якщо (a ,b) =1 , то числа взаємнопрості;

- числа a та b мають безкінечно багато чисел, кратних одночасно обом цім числам, найменше з кратних носить назву найменшого спільного кратного чисел a та b - [a ,b];

- [a ,b]= ( ab ) ; a ,b

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

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

де pi - різні за значенням прості числа, ai - степені входження відповідного простого числа pi до числа a , i = 1,k ;

- будь-яке раціональне число m можна розкласти у скінчений неперервний n

дріб, а будь-яке ірраціональне число – у нескінчений;

-будь-який раціональний дріб m на числовій осі розташований між двох його

n

підходящих дробів, ближче до правого краю.

Після вивчення теми 1 ви повинні вміти:

-знайти НСД за допомогою алгоритму Евкліда;

-застосувати найстаріший метод відбору простих чисел, менших за дане – решето Ератосфена;

-зробити факторізацію невеликих цілих чисел за допомогою ознак подільності чисел;

-виходячи з канонічної форми кількох цілих чисел знайти їх НСД та НСК;

17

- використовуючи таблицю підходящих дробів знайти розв’язок рівняння ax + by = d ;

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

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

1.Дати визначення простого числа, складеного числа, неповної частки, залишку.

2.Сформулювати основні властивості подільності чисел.

3.Сформулювати теорему про ділення з залишком.

4.В чому полягає різниця між взаємно простими і попарно простими числами?

5.Дати визначення спільного дільника довільного набору цілих чисел a , b, c , d .

6.Дати означення найбільшого спільного дільника (a ,b).

7.Спираючись на властивості подільності чисел довести, що якщо числа a , b можна зв’язати рівністю a = b × q + r , то (a ,b) = (b,r ) .

8.Сформулювати алгоритм Евкліда для знаходження (a ,b).

9.Відомо, що a - довільне число, а p - просте число. Які можливі варіанти (a , p)?

10.Дати визначення найменшого спільного кратного [a ,b]. Який існує зв’язок між

(a ,b) та [a ,b]?

11.Яке обмеження існує на найменший дільник числа a ?

12.Сформулювати теорему про єдиність канонічного розкладання довільного цілого числа a на прості множники.

13.Що таке неперервний дріб?

14.Довести, що неперервний дріб для раціонального числа завжди має скінчену довжину. Чи вірно це для ірраціональних чисел? Обґрунтуйте свою думку.

15.Що таке підходящий дріб. Якщо взяти два сусідніх підходящих дроба, то де буде розташоване вихідне число?

16.Сформулюйте самостійно схему обчислення підходящих дробів для довільного нескорочуваного раціонального дробу.

17.Які властивості мають підходящі дроби?

18.Використовуючи схему розкладання раціонального числа на неперервні дроби знайти для двох чисел 197 та 23 розв’язок рівняння 197x + 23y = 1.

18

ТЕМА №2 НАЙВАЖЛИВІШІ ФУНКЦІЇ В ТЕОРІЇ ЧИСЕЛ.

Питання 1 Функції виділення цілої та дробової частини дійсного числа. Питання 2 Мультиплікативні функції.

Питання 3 Приклади мультиплікативних функцій.

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

Функція виділення цілої частини, функція виділення дробової частини, мультиплікативні функції, кількість дільників, сума додатних дільників, недостатнє число, надлишкове число, досконале число, число Мерсенна, дружні числа, функція Ейлера.

Питання 1. Функції виділення цілої та дробової частини дійсного числа.

1. Функція виділення цілої частини дійсного числа х повертає найбільше ціле число, яке не перевищує х:

[x] = N; x = N + q; N Î Z; 0 < q < 1;

Приклади: [-100] = -100; [45,9] = 45; [- 5,1] = -6

2. Функція виділення дробової частини дійсного числа х повертає різницю між числом х та його цілою частиною [x]:

{x} = x - [x] = q; 0 < q < 1

Приклади: {-100} = 0; {45,9} = 0,9; {- 5,1} = 0,9

Приклад застосування функції виділення цілої частини:

Порахувавши усі степені 2, будемо мати: 1 + 2 + 1 + 3 + 1 = 8

19

Питання 2. Мультиплікативні функції.

Функція f (a) називається мультиплікативною, якщо для неї виконуються 2 умови:

Наприклад, задамо мультиплікативну функцію так: f (1) = 1, f (pα )= 2, "a > 0 . Тоді для

Доведення:

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

20