Eulers fi-funktion

Från Wikipedia
Hoppa till: navigering, sök
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 n = p_1^{k_1}..p_r^{k_r} där pj är distinkta primtal, då är

\varphi(n) = n \prod_{j=1}^r \left(1 - \frac{1}{p_j} \right)

Egenskaper hos φ(n)[redigera | redigera wikitext]

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

\sum_{d|n} \varphi(d) = 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

\phi(n) < e^{-\gamma}\frac  {n} {\log \log n}

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

Formler som innehåller φ(n)[redigera | redigera wikitext]

Delbarhet och elementära resultat[redigera | redigera wikitext]

  • Av a\mid b följer \varphi(a)\mid\varphi(b).
  •  n \mid \varphi(a^n-1)       (a, n > 1)
  • \varphi(mn) = \varphi(m)\varphi(n)\cdot\frac{d}{\varphi(d)}       där d = gcd(m, n). Notera specialfallen
  • 
\varphi(2m) = 
\begin{cases}
2\varphi(m) &\text{ om } m \text{ är jämn} \\
\varphi(m)   &\text{ om } m \text{ är udda}
\end{cases}

och

  • \;\varphi\left(n^m\right) = n^{m-1}\varphi(n).
  • \varphi(\mathrm{mgn}(m,n))\cdot\varphi(\mathrm{sgd}(m,n)) = \varphi(m)\cdot\varphi(n).      
Jämför med formeln       \mathrm{mgn}(m,n)\cdot \mathrm{sgd}(m,n) = m \cdot n.
  • \varphi(n)\; är jämn för n \geq 3. Dessutom, om n har r olika udda primtalsfaktorer, är 2^r \mid \varphi(n).
  • För alla a > 1 och n > 6 så att  4 \nmid n finns det ett  l \geq 2n så att  l \mid \varphi(a^n-1).

Summor som innehåller φ(n)[redigera | redigera wikitext]

  • \sum_{d \mid n} \frac{\mu^2(d)}{\varphi(d)} = \frac{n}{\varphi(n)}
  • \sum_{1\le k\le n \atop (k,n)=1}\!\!k = \frac{1}{2}n\varphi(n)\text{ för }n>1
  • \varphi(n)=\sum_{d\mid n} d \cdot \mu\left(\frac{n}{d} \right) =n\sum_{d\mid n} \frac{\mu (d)}{d}
  • \varphi (n)=\sum\limits_{k=1}^n \operatorname{sgd}(k,n) \cos {2\pi\frac{k}{n}}
  • \sum_{k=1}^n \varphi(k) = \frac{1}{2 \zeta(2)} n^2 + \mathcal{O}(n \log n)

där ζ är Riemanns zeta-funktion och \mathcal{O} är ordosymbolen. Av formeln följer approximationen \varphi(n) \approx n\frac{3}{\pi^2}.

  • \sum_{k=1}^n\varphi(k) = \frac{1}{2}\left(1+ \sum_{k=1}^n \mu(k)\left\lfloor\frac{n}{k}\right\rfloor^2\right)
  • \sum_{k=1}^n\frac{\varphi(k)}{k} = \sum_{k=1}^n\frac{\mu(k)}{k}\left\lfloor\frac{n}{k}\right\rfloor=\frac6{\pi^2}n+\mathcal{O}\left((\log n)^{2/3}(\log\log n)^{4/3}\right)
  • \sum_{k=1}^n\frac{k}{\varphi(k)} = \frac{315\zeta(3)}{2\pi^4}n-\frac{\log n}2+\mathcal{O}\left((\log n)^{2/3}\right)
  • \sum_{k=1}^n\frac{1}{\varphi(k)} = \frac{315\zeta(3)}{2\pi^4}\left(\log n+\gamma-\sum_{p\text{ primtal}}\frac{\log p}{p^2-p+1}\right)+\mathcal{O}\left(\frac{(\log n)^{2/3}}n\right)

(där γ är Eulers konstant).

  • \sum_{1\le k\le n \atop (k,m)=1} 1 = n \frac {\varphi(m)}{m} + 
\mathcal{O} \left ( 2^{\omega(m)} \right ),

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

Menons identitet[redigera | redigera wikitext]


\sum_{\stackrel{1\le k\le n}{ \operatorname{sgd}(k,n)=1}} \gcd(k-1,n)
=\varphi(n)d(n)

Formler som innehåller det gyllene snittet[redigera | redigera wikitext]

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


\phi=-\sum_{k=1}^\infty\frac{\varphi(k)}{k}\log\left(1-\frac{1}{\phi^k}\right)

och


\frac{1}{\phi}=-\sum_{k=1}^\infty\frac{\mu(k)}{k}\log\left(1-\frac{1}{\phi^k}\right).

Genom att subtrahera dem fås


\sum_{k=1}^\infty\frac{\mu(k)-\varphi(k)}{k}\log\left(1-\frac{1}{\phi^k}\right)=1.

Ett direkt korollarium är

e= \prod_{k=1}^{\infty} \left(1-\frac{1}{\phi^k}\right)^\frac{\mu(k)-\varphi(k)}{k}.

Bevisen baserar sig på formlerna


\sum_{k=1}^\infty\frac{\varphi(k)}{k}(-\log(1-x^k))=\frac{x}{1-x}
    och     
\sum_{k=1}^\infty\frac{\mu(k)}{k}(-\log(1-x^k))=x, 
    som gäller för 0 < x < 1.

Genererande funktioner[redigera | redigera wikitext]

Eulers fi-funktion har de genererande funktionerna

\sum_{n=1}^\infty \frac{\varphi(n)}{n^s}=\frac{\zeta(s-1)}{\zeta(s)}.

och

\sum_{n=1}^{\infty} \frac{\varphi(n) q^n}{1-q^n}= \frac{q}{(1-q)^2}

som konvergerar för |q| < 1.

Kvoten av konsekutiva värden[redigera | redigera wikitext]

1950 bevisade Somayajulu att


\lim\inf \frac{\varphi(n+1)}{\varphi(n)}= 0
        och        

\lim\sup \frac{\varphi(n+1)}{\varphi(n)}= \infty.

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


\left\{\frac{\varphi(n+1)}{\varphi(n)},\;\;n = 1,2,\cdots\right\}

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


\left\{\frac{\varphi(n)}{n},\;\;n = 1,2,\cdots\right\}

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

Olösta problem[redigera | redigera wikitext]

Lehmers förmodan[redigera | redigera wikitext]

If 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[redigera | redigera wikitext]

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 10^{10^{10}}.

Se även[redigera | redigera wikitext]