НСД (x, п) = 1}.

Справді, якщо НСД(х, n)=1, то wx-wn=1, де и, v - цілі числа. Звідси ux=l(mod n), і тоді елемент x-1 = u(mod п) є оберненим до х в Zn. Якщо НСД(х, п) = р > 1, то х не має оберненого елемента за модулем n, оскільки и х mod n є числом вигляду wx- vn, а, отже, ділиться на р.

Нехай ц(п) - кількість натуральних чисел, які менші від п і взаємно прості з n. Функцію ц називають функцією Ейлера. Якщо р - просте число, то ц(р) - р - 1. Легко перевірити, що коли р, q (р ? q) - прості числа, то ц(pq) = (р - l)(g - 1). Це випливає з того, що числа, які мають спільні з pq дільники, відмінні від 1, - це числа вигляду р, 2p,...,p(q-1),q,2q,..,q(p-1).

Твердження 3.3. (Вираз для функції Ейлера). Нехай п - натуральне число і нехай, де р1...,рl - прості числа. Тоді ц(п) = п{1 - 1/р1)...(1 - 1/рl).

Наприклад, нехай l = 1 (n = рб). Тоді числа, що менші або дорівнюють п і не взаємно прості з п, - це числа вигляду р, 2р, Зр, ..., ра; ра = ра-1 р. Отже, кількість цих чисел ра-1 Звідси випливає, що ц(ра) -ра - ра-1 = ра (1 - 1 / р).

Твердження 3.4. (Ейлер, 1763 p.). Для взаємно простих цілого х і натурального п виконується конгруенція хц(n)= 1 (mod n).

Оскільки для простого числа р ц(р) =р - 1, то отримуємо таке твердження.

Твердження 3.5. (мала теорема Ферма, 1640p.). Якщо р - просте число і ціле х не ділиться на р, то хp-1= 1 (mod p).

Приклад 3.5. Перевірити виконання конгруенції 4130= 1 (mod 31). Маємо таке:

1) 412(mod31) ?l02(mod31) ? 7(mod31);

414(mod 31) ? 72(mod 31) ? 18(mod 31);

418(mod31) ?182(mod31) ?14(mod31);

4116(mod 31) ? 142(mod 31) ? 10(mod 31);

2) оскільки 30 = 16 + 8 + 4 + 2, то 4130(mod 31) ? (4116418414412)(mod 31) ? (101418'7)(mod 31) ? 17640(mod 31) ? (569-31 + I)(mod31) ?l.

Твердження 3.6. (Китайська теорема про залишки, І ст. до н. є.). Нехай n1,n2 -взаємно прості цілі числа, а x1, х2- довільні цілі числа. Тоді існує лише одне таке число x що х?х1 (mod n1), х?x2(mod п2).

Справді, якщо НСД(n1,n2)= 1> то u1n1-u2n2 =1 де u1,u2 - цілі числа. Маємо u1n1 ?l(mod п2) і и2п2 ? l(mod n1). Звідси отримуємо х = x2 и1п1- x1 и2п2 оскільки х?-x1u2n2(mod n1) ?x1(mod n1), x?-x2u1n1(mod n2) ?x2(mod n2).

Приклад 3.6. Визначити таке ціле число х, що х= 100(mod 211) та as 10(mod 79).

З алгоритму Евкліда випливає 1 = 3*211-879. Маємо n1 =211, и1=3, n2 = 79, и2 = 8, а звідси отримуємо х = 10*3*211 – 8*79 = -56870. Оскільки -56870 (mod 211*79) = -56780(mod 16669) == 9806, то х = 9806.

Порядком елемента х є Zp* називають таке найменше натуральне число к, що xk=1(тоd р).

Нехай G довільна не порожня підмножина множини Zp*. Елемент g є G назива-ють твірною множини G, якщо для кожного х є G знайдеться таке натуральне число i, для якого х = gi(mod p). Зрозуміло, що порядок твірної множини G збігається з кіль-кістю елементів у множині G.

Твердження 3.7. Нехай р — просте число. Тоді існує твірна g множини Zp*,. Оскільки у множині Zp* є р- 1 елементів, то елементи

g° mod p? 1, g1 mod p, g2 mod p, g2 mod p, ... , gp-2 mod p

є попарно різними елементами множини Zp*.

Є багато твірних у множині Zp*. Якщо g є твірною, то й gi є твірною, коли НСД(i,р- 1)=1.

Приклад 3.7. Нехай р = 23. Тоді g = 5 є твірною в Z23*,.

Справді, 50 mod 23 = 1, 51 mod 23 = 5, 52 mod 23 = 2, 53 mod 23 ? 2-5 ?10. Насту-пні степені числа g = 5 за модулем р = 23 такі: 4, 20, 8, 17, 16, 11, 9, 22, 18, 21, 13, 19, З, 15.6,7,12,14.

З малої теореми Ферма випливає, що для кожного х є Z*23 виконується конгру-енція х22 =1 (mod 23).

Нехай р - просте число, і нехай р -1 = qa1...qa1 , де q1, ..., ql - прості числа. Тоді число g буде твірною множини Zp*., якщо для кожного 1 <і<l виконується умова g(p-1)/q ? l mod p.

Приклад 3.8. Нехай p = 29. Тоді 29-1=22*7. Оскільки 214 = 28(mod 29) і 24 = 16(mod 29), то g = 2 буде твірною в Z29.* Число g = 5 не є твірною, бо 514 = l(mod 29).

Кажемо, що y є квадратичним залишком за модулем п, якщо НСД(y, n) = 1 та існує таке х, що х2 = y(mod п). У такому випадку кажемо також, що х є первісним коренем з у за модулем п.

Приклад 3.9. Число 8 є квадратичним залишком за модулем 17, а число 5 є первісним коренем з 8 mod 17.

Твердження 3.8. Нехай р - просте число і х2= l(mod p). Тоді x? l(mod р) або х2 = -l(mod p).

Твердження 3.9. Нехай р > 2 -