Jak obliczyć funkcję Eulera?

Funkcję Eulera φ(n) oblicza się, rozkładając n na czynniki pierwsze i wykorzystując wzór φ(n) = n · ∏(1 − 1/p), gdzie p oznacza każdy różny czynnik pierwszy liczby n.

Czym jest funkcja Eulera?

Funkcja Eulera φ(n) określa, ile dodatnich liczb całkowitych k spełnia warunek 1 ≤ k ≤ n oraz NWD(k, n) = 1. Liczby spełniające ten warunek są względnie pierwsze z n, czyli nie mają z n wspólnego dzielnika większego od 1.

Jeżeli rozkład liczby n ma postać:

n = p₁^k₁ · p₂^k₂ · … · p_r^k_r,

gdzie p₁, p₂, …, p_r są różnymi czynnikami pierwszymi, wtedy:

φ(n) = n · (1 − 1/p₁) · (1 − 1/p₂) · … · (1 − 1/p_r).

W obliczeniach uwzględnia się tylko różne czynniki pierwsze. Ich wykładniki nie pojawiają się bezpośrednio w nawiasach. Dla liczby pierwszej p wzór upraszcza się do φ(p) = p − 1.

Jak obliczyć φ(n) krok po kroku?

Obliczenie dla dowolnej dodatniej liczby całkowitej n można wykonać według następującej procedury:

1. Rozłóż n na czynniki pierwsze – zapisz liczbę jako iloczyn potęg liczb pierwszych.
2. Wypisz różne czynniki pierwsze – pomiń powtórzenia wynikające z ich wykładników.
3. Podstaw je do wzoru – dla każdego czynnika p użyj wyrażenia (1 − 1/p).
4. Pomnóż otrzymane wartości przez n – wynik jest wartością funkcji Eulera φ(n).

Przykładowo, dla n = 18 rozkład wynosi 18 = 2 · 3². Różne czynniki pierwsze to 2 i 3, więc:

φ(18) = 18 · (1 − 1/2) · (1 − 1/3) = 18 · 1/2 · 2/3 = 6.

Przykłady obliczeń funkcji Eulera

Poniższe zestawienie pokazuje przypadek liczby pierwszej oraz liczb złożonych:

Dla n = 12 czynnik 2 występuje w rozkładzie jako 2², ale we wzorze pojawia się tylko raz. To właśnie różne czynniki pierwsze decydują o postaci iloczynu.

Co decyduje o trudności obliczenia?

Sam wzór jest prosty. Najwięcej pracy może wymagać znalezienie rozkładu n na czynniki pierwsze. Gdy czynniki są już znane, wystarczy podstawić je do wzoru i wykonać działania.

Najważniejsza zasada brzmi: rozłóż n na czynniki pierwsze, wybierz każdy z nich tylko raz, a następnie zastosuj φ(n) = n · ∏(1 − 1/p).