Funkcja fi Eulera.

Wprowadzenie funkcji fi Eulera.

Euler zajmował się między innymi właściwościami liczb -

w szczególności rozmieszczeniem liczb pierwszych.

Istotną funkcją, którą wprowadził

jest funkcja 'fi' Eulera.

Mierzy ona jak bardzo dana liczba da się rozkładać.

Dla danej liczby n,

zwraca ile mamy liczb naturalnych mniejszych lub równych liczbie n,

które nie mają z nią żadnych wspólnych dzielników.

Dla przykładu, jeśli chcemy policzyć fi(8),

to patrzymy na wszystkie liczby od 1 do 8,

i liczymy ile z nich,

nie posiada wspólnego dzielnika z 8 większego od 1.

Zauważmy, że 6 nie jest wliczane,

ponieważ 6 oraz 8 mają wspólny dzielnik równy 2,

podczas gdy 1, 3, 5 oraz 7 się wliczają,

ponieważ każda z nich posiada największy wspólny dzielnik z 8 równy 1.

Stąd, fi(8) jest równe 4.

Interesującym faktem jest, że

obliczanie funkcji fi jest trudne, za wyjątkiem jednego przypadku.

Spójrz na ten wykres.

Jest to wykres wartości funkcji fi dla liczb naturalnych od 1 do 1000.

Zauważasz pewien schemat?

Prosta linia punktów na górze,

reprezentuje wartości dla liczb pierwszych.

Liczby pierwsze nie mają wspólnych dzielników większych od 1, z liczbami od siebie mniejszymi,

więc fi od liczby pierwszej p wynosi po prostu p-1.

Aby obliczyć fi(7) - która jest liczbą pierwszą -

liczymy wszystkie liczby mniejsze od 7,

ponieważ żadna z nich nie ma wspólnego dzielnika z 7, większego od 1.

stąd fi(7) = 6

Więc jeśli ktoś zapyta ile wynosi fi(21377), czyli od liczby pierwszej,

należy tylko od niej odjąć 1, aby dostać odpowiedź,

w tym przypadku jest to 21 376.

fi od dowolnej liczby pierwszej jest łatwo obliczyć,

co prowadzi do innego ciekawego wyniku, że

funkcja fi jest 'multiplikatywna'.

Co znaczy, że fi(A x B) = phi(A) x phi(B), gdzie NWD(A,B) = 1.

Jeśli znamy jakąś liczbę N,

która jest iloczynem dwóch liczb pierwszych P1 oraz P2,

to fi(N) jest po prostu wynikiem,

iloczynu fi od każdej z tych liczb.

czyli (P1 - 1) x (P2 - 1).