Från Rilpedia

Eulers φ-funktion φ(n), namngiven efter Leonhard Euler, är en viktig aritmetisk funktion inom talteorin.

Om n är ett positivt heltal, då definieras φ(n) som antalet positiva heltal mindre än eller lika med n som är relativt prima med n. Till exempel är φ(8) = 4 eftersom de fyra talen 1, 3, 5 och 7 är relativt prima till 8.

φ är en multiplikativ funktion då m och n är relativt prima dvs φ(mn) = φ(m) φ(n).

Värdet av φ(n) kan därför beräknas genom att använda aritmetikens fundamentalsats dvs om där p_j är distinkta primtal, då är

Värdet av φ(n) är lika med ordningen av enhetsgruppen till ringen Z/nZ (se modulär aritmetik). Detta tillsammans med Lagranges teorem, ger ett bevis för Eulers sats.

Egenskaper hos φ(n)

∑	φ(d) = n
d | n,d > 0