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
n
=
p
1
k
1
.
.
p
r
k
r
{\displaystyle n=p_{1}^{k_{1}}..p_{r}^{k_{r}}}
p j primtal , då är
φ
(
n
)
=
n
∏
j
=
1
r
(
1
−
1
p
j
)
{\displaystyle \varphi (n)=n\prod _{j=1}^{r}\left(1-{\frac {1}{p_{j}}}\right)}
Om man summerar φ:s värden för alla positiva heltal som delar ett tal n får man talet n :
∑
d
|
n
φ
(
d
)
=
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 /n Z (se modulär aritmetik ). Detta tillsammans med Lagranges sats ger ett bevis för Eulers sats .
1983 bevisade J. L. Nicolas att
ϕ
(
n
)
<
e
−
γ
n
log
log
n
{\displaystyle \phi (n)<e^{-\gamma }{\frac {n}{\log \log n}}}
gäller för oändligt många n där γ är Eulers konstant .
redigera
Av
a
∣
b
{\displaystyle a\mid b}
φ
(
a
)
∣
φ
(
b
)
.
{\displaystyle \varphi (a)\mid \varphi (b).}
n
∣
φ
(
a
n
−
1
)
{\displaystyle n\mid \varphi (a^{n}-1)}
a , n > 1)
φ
(
m
n
)
=
φ
(
m
)
φ
(
n
)
⋅
d
φ
(
d
)
{\displaystyle \varphi (mn)=\varphi (m)\varphi (n)\cdot {\frac {d}{\varphi (d)}}}
d = sgd(m , n ). Notera specialfallen
φ
(
2
m
)
=
{
2
φ
(
m
)
om
m
är jämn
φ
(
m
)
om
m
är udda
{\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
φ
(
n
m
)
=
n
m
−
1
φ
(
n
)
.
{\displaystyle \;\varphi \left(n^{m}\right)=n^{m-1}\varphi (n).}
φ
(
m
g
n
(
m
,
n
)
)
⋅
φ
(
s
g
d
(
m
,
n
)
)
=
φ
(
m
)
⋅
φ
(
n
)
.
{\displaystyle \varphi (\mathrm {mgn} (m,n))\cdot \varphi (\mathrm {sgd} (m,n))=\varphi (m)\cdot \varphi (n).}
Jämför med formeln
m
g
n
(
m
,
n
)
⋅
s
g
d
(
m
,
n
)
=
m
⋅
n
.
{\displaystyle \mathrm {mgn} (m,n)\cdot \mathrm {sgd} (m,n)=m\cdot n.}
φ
(
n
)
{\displaystyle \varphi (n)\;}
n
≥
3.
{\displaystyle n\geq 3.}
n har r olika udda primtalsfaktorer, är
2
r
∣
φ
(
n
)
.
{\displaystyle 2^{r}\mid \varphi (n).}
För alla a > 1 och n > 6 så att
4
∤
n
{\displaystyle 4\nmid n}
l
≥
2
n
{\displaystyle l\geq 2n}
l
∣
φ
(
a
n
−
1
)
{\displaystyle l\mid \varphi (a^{n}-1)}
∑
d
∣
n
μ
2
(
d
)
φ
(
d
)
=
n
φ
(
n
)
{\displaystyle \sum _{d\mid n}{\frac {\mu ^{2}(d)}{\varphi (d)}}={\frac {n}{\varphi (n)}}}
∑
1
≤
k
≤
n
(
k
,
n
)
=
1
k
=
1
2
n
φ
(
n
)
för
n
>
1
{\displaystyle \sum _{1\leq k\leq n \atop (k,n)=1}\!\!k={\frac {1}{2}}n\varphi (n){\text{ för }}n>1}
φ
(
n
)
=
∑
d
∣
n
d
⋅
μ
(
n
d
)
=
n
∑
d
∣
n
μ
(
d
)
d
{\displaystyle \varphi (n)=\sum _{d\mid n}d\cdot \mu \left({\frac {n}{d}}\right)=n\sum _{d\mid n}{\frac {\mu (d)}{d}}}
φ
(
n
)
=
∑
k
=
1
n
sgd
(
k
,
n
)
cos
2
π
k
n
{\displaystyle \varphi (n)=\sum \limits _{k=1}^{n}\operatorname {sgd} (k,n)\cos {2\pi {\frac {k}{n}}}}
∑
k
=
1
n
φ
(
k
)
=
1
2
ζ
(
2
)
n
2
+
O
(
n
log
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
O
{\displaystyle {\mathcal {O}}}
ordosymbolen . Av relationen följer approximationen
φ
(
n
)
≈
n
3
π
2
.
{\displaystyle \varphi (n)\approx n{\frac {3}{\pi ^{2}}}.}
∑
k
=
1
n
φ
(
k
)
=
1
2
(
1
+
∑
k
=
1
n
μ
(
k
)
⌊
n
k
⌋
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)}
∑
k
=
1
n
φ
(
k
)
k
=
∑
k
=
1
n
μ
(
k
)
k
⌊
n
k
⌋
=
6
π
2
n
+
O
(
(
log
n
)
2
/
3
(
log
log
n
)
4
/
3
)
{\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)}
∑
k
=
1
n
k
φ
(
k
)
=
315
ζ
(
3
)
2
π
4
n
−
log
n
2
+
O
(
(
log
n
)
2
/
3
)
{\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)}
∑
k
=
1
n
1
φ
(
k
)
=
315
ζ
(
3
)
2
π
4
(
log
n
+
γ
−
∑
p
primtal
log
p
p
2
−
p
+
1
)
+
O
(
(
log
n
)
2
/
3
n
)
{\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 ).
∑
1
≤
k
≤
n
(
k
,
m
)
=
1
1
=
n
φ
(
m
)
m
+
O
(
2
ω
(
m
)
)
,
{\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 .
∑
sgd
(
k
,
n
)
=
1
1
≤
k
≤
n
gcd
(
k
−
1
,
n
)
=
φ
(
n
)
d
(
n
)
{\displaystyle \sum _{\stackrel {1\leq k\leq n}{\operatorname {sgd} (k,n)=1}}\gcd(k-1,n)=\varphi (n)d(n)}
Några identiteter av Schneider som innehåller Eulers fi-funktion, Möbiusfunktionen och det gyllene snittet är
ϕ
=
−
∑
k
=
1
∞
φ
(
k
)
k
log
(
1
−
1
ϕ
k
)
{\displaystyle \phi =-\sum _{k=1}^{\infty }{\frac {\varphi (k)}{k}}\log \left(1-{\frac {1}{\phi ^{k}}}\right)}
och
1
ϕ
=
−
∑
k
=
1
∞
μ
(
k
)
k
log
(
1
−
1
ϕ
k
)
.
{\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
∑
k
=
1
∞
μ
(
k
)
−
φ
(
k
)
k
log
(
1
−
1
ϕ
k
)
=
1.
{\displaystyle \sum _{k=1}^{\infty }{\frac {\mu (k)-\varphi (k)}{k}}\log \left(1-{\frac {1}{\phi ^{k}}}\right)=1.}
Ett direkt korollarium är
e
=
∏
k
=
1
∞
(
1
−
1
ϕ
k
)
μ
(
k
)
−
φ
(
k
)
k
.
{\displaystyle e=\prod _{k=1}^{\infty }\left(1-{\frac {1}{\phi ^{k}}}\right)^{\frac {\mu (k)-\varphi (k)}{k}}.}
Bevisen baserar sig på formlerna
∑
k
=
1
∞
φ
(
k
)
k
(
−
log
(
1
−
x
k
)
)
=
x
1
−
x
{\displaystyle \sum _{k=1}^{\infty }{\frac {\varphi (k)}{k}}(-\log(1-x^{k}))={\frac {x}{1-x}}}
∑
k
=
1
∞
μ
(
k
)
k
(
−
log
(
1
−
x
k
)
)
=
x
,
{\displaystyle \sum _{k=1}^{\infty }{\frac {\mu (k)}{k}}(-\log(1-x^{k}))=x,}
x < 1.
Eulers fi-funktion har de genererande funktionerna
∑
n
=
1
∞
φ
(
n
)
n
s
=
ζ
(
s
−
1
)
ζ
(
s
)
.
{\displaystyle \sum _{n=1}^{\infty }{\frac {\varphi (n)}{n^{s}}}={\frac {\zeta (s-1)}{\zeta (s)}}.}
och
∑
n
=
1
∞
φ
(
n
)
q
n
1
−
q
n
=
q
(
1
−
q
)
2
{\displaystyle \sum _{n=1}^{\infty }{\frac {\varphi (n)q^{n}}{1-q^{n}}}={\frac {q}{(1-q)^{2}}}}
som konvergerar för |q | < 1.
1950 bevisade Somayajulu att
lim
inf
φ
(
n
+
1
)
φ
(
n
)
=
0
{\displaystyle \lim \inf {\frac {\varphi (n+1)}{\varphi (n)}}=0}
lim
sup
φ
(
n
+
1
)
φ
(
n
)
=
∞
.
{\displaystyle \lim \sup {\frac {\varphi (n+1)}{\varphi (n)}}=\infty .}
1954 bevisade Schinzel och Sierpiński det starkare resultatet att mängden
{
φ
(
n
+
1
)
φ
(
n
)
,
n
=
1
,
2
,
⋯
}
{\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
{
φ
(
n
)
n
,
n
=
1
,
2
,
⋯
}
{\displaystyle \left\{{\frac {\varphi (n)}{n}},\;\;n=1,2,\cdots \right\}}
är tät i intervallet (0, 1).
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 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
{\displaystyle 10^{10^{10}}}
