1.5 Функція Ейлера

Важливу роль у теорії чисел відіграє функція Ейлера.

Визначення. Функцією Ейлера називається функція, що визначає для кожного числа nN кількість цілих невід’ємних чисел менших n і взаємно простих з n.

Властивості функції Ейлера:

1. Функція мультиплікативна, тобто для функція і для будь-яких взаємно простих чисел m, n (m, nN) справедлива рівність

.

2. Якщо p – просте число та , то

.

3. Якщо канонічне розкладання числа nN має вигляд

,

то

.

Наприклад,

4. Сума значень функції Ейлера для всіх дільників числа n дорівнює n, тобто

.

1.6 Порівняння в кільці цілих чисел

Визначення. Два числа називаються порівнянними за модулем m (mN, m1), якщо . Це записують так:

.

Теорема 6 Два числа порівнянні за модулем m тоді і тільки тоді, коли вони при діленні на m мають однакові залишки.

Доведення. Припустимо, залишки від ділення a та b на m рівні r (0r<m). Покажемо, що . Розділимо a на m та b на m з остачею. Одержимо

Віднімемо почленно

, Z.

Звідси випливає, що . А значить .

Обернено. Нехай . Покажемо, що числа a і b при діленні на m мають ту саму остачу. З того, що , випливає . За визначенням подільності

, (1.3)

де .

Розділимо число b на m, одержимо

, (0r<m). (1.4)

Підставимо рівність (1.4) у рівність (1.3). Одержимо

Таким чином, видно, що число a при діленні на m має той самий залишок, що і число b. Теорема доведена.

Відзначимо найбільш часто використовувані факти.

Якщо , то , а це значить, що , тобто будь-яке число, кратне m порівняно з нулем за модулем  m.

Якщо , де 0r<m, то . Таким чином, завжди порівняно з залишком r, що отримано при діленні a на m.

Часто залишок r називають відрахуванням.

Розглянемо деякі властивості порівнянь.

Властивості порівнянь, що не залежать від модуля m.

1. Відношення є відношенням еквівалентності, тобто задовольняє вимоги:

   • рефлексивності: ;

   • симетричності: ;

   • транзитивності: .