Eulers fi-funktion

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

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

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 ${\displaystyle n=p_{1}^{k_{1}}..p_{r}^{k_{r}}}$ där p_j är distinkta primtal, då är

${\displaystyle \varphi (n)=n\prod _{j=1}^{r}\left(1-{\frac {1}{p_{j}}}\right)}$

Egenskaper hos φ(n)

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

${\displaystyle \sum _{d|n}\varphi (d)=n\,}$

φ är en multiplikativ funktion då m 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

${\displaystyle \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)

Delbarhet och elementära resultat

• Av ${\displaystyle a\mid b}$ följer ${\displaystyle \varphi (a)\mid \varphi (b).}$

• ${\displaystyle n\mid \varphi (a^{n}-1)}$       (a, n > 1)

• ${\displaystyle \varphi (mn)=\varphi (m)\varphi (n)\cdot {\frac {d}{\varphi (d)}}}$       där d = sgd(m, n). Notera specialfallen
• ${\displaystyle \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

• ${\displaystyle \;\varphi \left(n^{m}\right)=n^{m-1}\varphi (n).}$

• ${\displaystyle \varphi (\mathrm {mgn} (m,n))\cdot \varphi (\mathrm {sgd} (m,n))=\varphi (m)\cdot \varphi (n).}$      

Jämför med formeln       ${\displaystyle \mathrm {mgn} (m,n)\cdot \mathrm {sgd} (m,n)=m\cdot n.}$

• ${\displaystyle \varphi (n)\;}$ är jämn för ${\displaystyle n\geq 3.}$ Dessutom, om n har r olika udda primtalsfaktorer, är ${\displaystyle 2^{r}\mid \varphi (n).}$

• För alla a > 1 och n > 6 så att ${\displaystyle 4\nmid n}$ finns det ett ${\displaystyle l\geq 2n}$ så att ${\displaystyle l\mid \varphi (a^{n}-1)}$.

Summor som innehåller φ(n)

• ${\displaystyle \sum _{d\mid n}{\frac {\mu ^{2}(d)}{\varphi (d)}}={\frac {n}{\varphi (n)}}}$

• ${\displaystyle \sum _{1\leq k\leq n \atop (k,n)=1}\!\!k={\frac {1}{2}}n\varphi (n){\text{ för }}n>1}$

• ${\displaystyle \varphi (n)=\sum _{d\mid n}d\cdot \mu \left({\frac {n}{d}}\right)=n\sum _{d\mid n}{\frac {\mu (d)}{d}}}$

• ${\displaystyle \varphi (n)=\sum \limits _{k=1}^{n}\operatorname {sgd} (k,n)\cos {2\pi {\frac {k}{n}}}}$

• ${\displaystyle \sum _{k=1}^{n}\varphi (k)={\frac {1}{2\zeta (2)}}n^{2}+{\mathcal {O}}(n\log n)}$

där ζ är Riemanns zetafunktion och ${\displaystyle {\mathcal {O}}}$ är ordosymbolen. Av relationen följer approximationen ${\displaystyle \varphi (n)\approx n{\frac {3}{\pi ^{2}}}.}$

• ${\displaystyle \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)}$

• ${\displaystyle \sum _{k=1}^{n}{\frac {\varphi (k)}{k}}=\sum _{k=1}^{n}{\frac {\mu (k)}{k}}\left\lfloor {\frac {n}{k}}\right\rfloor ={\frac {6}{\pi ^{2}}}n+{\mathcal {O}}\left((\log n)^{2/3}(\log \log n)^{4/3}\right)}$

• ${\displaystyle \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)}$

• ${\displaystyle \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).

• ${\displaystyle \sum _{1\leq k\leq 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

${\displaystyle \sum _{\stackrel {1\leq k\leq n}{\operatorname {sgd} (k,n)=1}}\gcd(k-1,n)=\varphi (n)d(n)}$

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

${\displaystyle \phi =-\sum _{k=1}^{\infty }{\frac {\varphi (k)}{k}}\log \left(1-{\frac {1}{\phi ^{k}}}\right)}$

och

${\displaystyle {\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

${\displaystyle \sum _{k=1}^{\infty }{\frac {\mu (k)-\varphi (k)}{k}}\log \left(1-{\frac {1}{\phi ^{k}}}\right)=1.}$

Ett direkt korollarium är

${\displaystyle e=\prod _{k=1}^{\infty }\left(1-{\frac {1}{\phi ^{k}}}\right)^{\frac {\mu (k)-\varphi (k)}{k}}.}$

Bevisen baserar sig på formlerna

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

Genererande funktioner

Eulers fi-funktion har de genererande funktionerna

${\displaystyle \sum _{n=1}^{\infty }{\frac {\varphi (n)}{n^{s}}}={\frac {\zeta (s-1)}{\zeta (s)}}.}$

och

${\displaystyle \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

1950 bevisade Somayajulu att

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

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

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

${\displaystyle \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

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

ä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 > 10²⁰ och att ω(n) ≥ 14. Dessutom bevisade Hagis att om 3 delar n är n > 10^1937042 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 ${\displaystyle 10^{10^{10}}}$.

Se även

• Duffin–Schaeffers förmodan