Funkcja φ (tocjent) Eulera

Euler badał właściwości liczb, zwłaszcza rozkład liczb pierwszych. Zdefiniował ważną funkcję, tzw. funkcję φ. Mierzy ona „rozbijalność” liczby. Dla danego N, funkcja φ określa, ile jest liczb całkowitych mniejszych od N lub równych N, niemających z nią wspólnych dzielników. Np. chcąc wyznaczyć wartość funkcji φ dla 8, sprawdzamy wszystkie liczby od 1 do 8. Patrzymy, ile liczb całkowitych nie ma z 8 wspólnego dzielnika większego niż 1. Nie policzymy 6, ze względu na wspólny dzielnik 2, za to 3, 5 i 7 pasują, bo wspólnym dzielnikiem jest tylko 1. Zatem φ policzone dla liczby 8 wynosi 4. Co ciekawe, obliczanie funkcji φ jest trudne poza jednym przypadkiem. Spójrzcie na wykres. Naniesiono wartości tej funkcji dla liczb całkowitych od 1 do 1000. Widzicie jakąś prawidłowość? Linia prosta punktów u góry to wszystkie liczby pierwsze. Ponieważ nie mają one czynników pierwszych większych od 1, to wartość φ dla każdej liczby pierwszej P wynosi po prostu P minus 1. Wartość funkcji φ dla 7, liczby pierwszej, to wszystkie liczby całkowite prócz 7, bo nie mają wspólnego dzielnika z 7. Zatem wartość funkcji φ dla 7 wynosi 6. Jeśli każą wam wyznaczyć wartość φ dla 21377, liczby pierwszej, wystarczy odjąć 1, by uzyskać rozwiązanie: 21376. Łatwo jest obliczyć wartość funkcji φ dla każdej liczby pierwszej. A to prowadzi do czegoś ciekawego, bo funkcja φ jest multiplikatywna. Czyli wartość funkcji φ policzona dla (A razy B) równa się φ policzona dla A razy φ policzona dla B. Jeśli wiemy, że N jest iloczynem dwóch liczb pierwszych, P1 i P2, to wartość funkcji φ dla N jest po prostu iloczynem wartości dla każdej z liczb. Czyli (P1 minus 1) razy (P2 minus 1).