Euler-féle Φ függvény

Euler tovább vizsgálta a számok tulajdonságait. Elsősorban a prímszámok eloszlását vizsgálta. Definiált egy fontos függvényt, a Φ függvényt, ami egy szám felbonthatóságát méri. Ha adott egy szám, például N, akkor a Φ függvény megadja azon N-nél kisebb vagy egyenlő egész számok számát, amelyeknek nincs közös osztójuk N-nel. Például, ha kíváncsiak vagyunk Φ(8)-ra, megnézzük a számokat 1-től 8-ig, és megszámoljuk azokat az egészeket, amiknek a 8-cal nincs az 1-en kívüli közös osztója. Figyeld meg, a 6-ot nem számoljuk, mert a 2 mindkét szám osztója, de az 1, 3, 5 és 7 mind számít, mert csak az 1 a közös osztójuk. ezért Φ(8) értéke 4. Ami még érdekes, hogy a Φ függvény számítása nehéz, kivéve egy esetet. Nézd meg ezt a grafikont! A Φ értékeket ábrázolja 1-től 1000-ig. Látsz valami megjósolható mintázatot? A felül levő egyenes vonal a prímszámokat jelöli. Mivel a prímszámoknak nincs 1-nél nagyobb osztója, bármely P prímszámra Φ értéke egyszerűen P-1. Φ(7) kiszámításához, ami prímszám, számítani fog a 7-en kívül az összes egész szám, mivel egyiknek se lesz közös osztója 7-tel. Φ(7) értéke 6. Ha meg kell állapítani Φ(21377) értékét, ami egy prímszám, csak ki kel vonni 1-et, és megkapod az eredményt, 21376-ot. Bármelyik prímszám Φ értékét könnyű kiszámolni. Ennek van egy érdekes következménye, aminek az az alapja, hogy a Φ függvény relatív prím számok esetén multiplikatív is. Ez azt jelenti, hogy Φ(A·B) = Φ(A) · Φ(B). Ha tudjuk, hogy egy N szám két prím szorzata, P1 · P2, akkor Φ(N) értéke a két prím Φ függvényértékének szorzata, azaz (P1-1) · (P2-1).