Eulers fi-funktion

De tusen första värdena av φ(n)

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.

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

Egenskaper hos φ(n)

Om man summerar φ:s värden för alla positiva heltal som delar ett tal n får man talet n:

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

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

1983 bevisade J. L. Nicolas att

gäller för oändligt många n där γ är Eulers konstant.

Formler som innehåller φ(n)

Delbarhet och elementära resultat

  • Av följer
  •       (a, n > 1)
  •       där d = sgd(m, n). Notera specialfallen

och

  •      
Jämför med formeln      
  • är jämn för Dessutom, om n har r olika udda primtalsfaktorer, är
  • För alla a > 1 och n > 6 så att finns det ett så att .

Summor som innehåller φ(n)

där ζ är Riemanns zetafunktion och är ordosymbolen. Av relationen följer approximationen

(där γ är Eulers konstant).

där m > 1 är ett positivt heltal och ω(m) är antalet olika primtalsfaktorer av m.

Menons identitet

Formler som innehåller det gyllene snittet

Några identiteter av Schneider som innehåller Eulers fi-funktion, Möbiusfunktionen och det gyllene snittet är

och

Genom att subtrahera dem fås

Ett direkt korollarium är

Bevisen baserar sig på formlerna

    och         som gäller för 0 < x < 1.

Genererande funktioner

Eulers fi-funktion har de genererande funktionerna

och

som konvergerar för |q| < 1.

Kvoten av konsekutiva värden

1950 bevisade Somayajulu att

        och        

1954 bevisade Schinzel och Sierpiński det starkare resultatet att mängden

är tät i mängden av positiva reella tal. De bevisade också att mängden

är tät i intervallet (0, 1).

Olösta problem

Lehmers förmodan

Om p är ett primtal är φ(p) = p − 1. 1932 frågade D. H. Lehmer om det finns några sammansatta tal n så att φ(n) | n − 1. Än så länge är inga såna är kända.

1933 bevisade han att om ett sådant n existerar måste det vara udda kvadratfritt och delbart med åtminstone sju primtal (det vill säga ω(n) ≥ 7). Cohen och Hagis bevisade 1980 att n > 1020 och att ω(n) ≥ 14. Dessutom bevisade Hagis att om 3 delar n är n > 101937042 och ω(n) ≥ 298848.

Carmichaels förmodan

Carmichaels förmodan säger att för alla positiva heltal n finns det åtminstone ett annat positivt heltal m ≠ n så att φ(m) = φ(n).

Det är känt att om det finns ett enda tal som inte satisfierar förmodan, då finns det oändligt många, och att det minsta eventuella talet som inte satisfierar förmodan är minst .

Se även

Media som används på denna webbplats

Question book-4.svg
Författare/Upphovsman: Tkgd2007, Licens: CC BY-SA 3.0
A new incarnation of Image:Question_book-3.svg, which was uploaded by user AzaToth. This file is available on the English version of Wikipedia under the filename en:Image:Question book-new.svg
EulerPhi.svg
Författare/Upphovsman: Pietro Battiston (it:User:Toobaz), Licens: CC BY-SA 4.0
Plot of the first 1000 values of the en:Euler's totient function. Svg version of Image:EulerPhi.PNG