Eulers fi-funktion
Från Rilpedia
(Omdirigerad från Eulers phi-funktion)
Texten från svenska Wikipedia
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 pj ä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 |
