9. Функція Ейлера та її властивості. Теорема про мультиплікативність функції Ейлера.

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

Властивості.

1. Якщо p – просте число, то (p)=p-1. Доведення випливає з означення функції Ейлера.

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

Д-ня. Випишемо всі натуральні числа від 1 до p^α та розіб’ємо їх на групи по p чисел {1,2,3,…p}, {p+1,p+2,…2p} …{p^α+p+1,…p^α}. Очевидно, що всіх груп буде p^α-1 ()

Очевидно, що в кожній групі всі числа, крім одного (останнього) взаємно прості з p^α. Отже всіх чисел взаємно простих з p^α буде (p-1)p^α-1 тобто ▲

3. Функція Ейлера мультиплікативна.

Д-ня. Для доведеня цього факту достатньо показати, що для довільних m,nє N і (m,n)=1 φ(mn)=φ(m)φ(n). Випишемо всі числа, які не перевищують mn та з’ясуємо, які з них взаємно прості з mn. Зрозуміло, що число взаємно просте з mn тоді і тільки тоді, коли воно взаємно просте з m і з n. Розташуємо числа від 1 до mn у таблицю, з’ясуємо скільки чисел взаємно простих з m міститься у таблиці

1 2 … r … m

m+1, m+2 … m+r … 2m

2m+1, 2m+2 … 2m+r … 3m

………………………………………….

(n-1)m+1, (n-1)m+2 … (n-1)m+r …mn

Для цього покажемо, що в кожному стовпчику всі числа або одночасно взаємно прості з m або не взаємно прості. Виберемо довільний r-тий стовпчик, всі числа цього стовпчика мають вигляд: km+r, 0≤k≤n-1. За властивістю НСД двох чисел (a=bq+r (a,b)=(b,r)) маємо (km+r,m)=(m,r). Отже НСД всіх чисел стовпчика з числом m той же самий, що і з числом r і визначається номером стовпчика (числом r). Таким чином кількість стовпчиків у яких всі числа взаємно прості з m буде стільки ж скільки взаємно простих чисел міститься у першому рядку, а їх буде φ(m). Покажемо, що всі числа у довільно вибраному стовпці при діленні на n дають різні остачі. Нехай це не так і якийсь стовпець має 2 числа, що дають однакові остачі при діленні на n. _ k₁m+r=nq₁+s

k₂m+r=nq₂+s

m(k₁-k₂)=n(q₁-q₂)

(0≤k₁,k₂…≤n-1, k₁≠k₂, 0≤ s ≤0)

Оскільки права частина ділиться на n і (m,n)=1 то (k1-k2)÷n. Проте |k₁-k₂|<n звідки k₁-k₂=0 і k₁=k₂, що суперечить припущенню. Отже всі числа в стовпці дають попарно різні остачі при при діленні на n: 0, 1, 2,… n-1. Отже серед чисел стовпця взаємно простих з n буде стільки ж, скільки є взаємно простих чисел від 1 до n, а їх φ(n). Таким чином у таблиці міститься φ(m) взаємно простих з m стовпчиків і в кожному стовпчику φ(n) чисел, які взаємно прості з n, отже всіх взаємно простих з mn чисел буде φ(m)φ(n). Звідки φ(mn)=φ(m)φ(n).▲

4. Якщо n=p^α1₁p^α2₂…p^αk_k то

φ(n)=n(1-)(1-)…(1-)

Д-ня. В силу мультиплікативності функції φ, φ(n)=φ(p^α1₁p^α2₂…p^αk_k ) = φ(p^α1₁)φ(p^α2₂)…φ(p^αk_k) за властивістю 2

φ(n)= p^α1₁ (1-) p^α2₂ (1-)… p^αk_k (1-)=n(1-)(1-)…(1-)

▲

5. Формула Гауса

Д-ня. (1+ φ(p₁)+φ(p₁²)+…

+φ(p₁^α1))(1+φ(p₂)+…+φ(p₂^α2))…(1+ +φ(p_k)+…+φ(p_k^αk))=(1+p₁-1+p₁²-p₁+… +p₁^α1-p₁^α1-1)(1-p₂-1+…+p₂^α2-p₂^α2-1)… (1+p_k-1+…+p_k^αk-p_α^k-1)=p₁^α1p₂^α2…p_k^αk=n

▲

6. При n > 2 φ(n) є числом парним.