Talteori
Definition: Ett heltal
a
{\displaystyle a}
säges vara delbart med ett heltal
b
{\displaystyle b}
om det existerar ett tal
k
{\displaystyle k}
s.a.
a
=
b
⋅
k
{\displaystyle a=b\cdot k}
(vilket kompakt kan skrivas
∃
k
:
a
=
b
⋅
k
{\displaystyle \exists k:a=b\cdot k}
). Detta skrives
a
|
b
{\displaystyle a|b}
. a delar b. b är en delare till a.
Definition: En äkta delare till ett tal
a
{\displaystyle a}
är ett positivt heltal
d
∉
{
1
,
p
}
:
d
|
a
{\displaystyle d\notin \{1,p\}:d|a}
.
Notation: Den största gemensamma delaren till
a
{\displaystyle a}
och
b
{\displaystyle b}
betecknas
(
a
,
b
)
{\displaystyle (a,b)}
.
Kongruenser
Definition:
a
≡
b
(
mod
n
)
{\displaystyle a\equiv b{\pmod {n}}}
definieras som
n
|
(
b
−
a
)
{\displaystyle n|(b-a)}
.
Sats: Om
a
≡
b
(
mod
n
)
{\displaystyle a\equiv b{\pmod {n}}}
,
c
{\displaystyle c}
heltal, så
a
+
c
≡
b
+
c
(
mod
n
)
{\displaystyle a+c\equiv b+c{\pmod {n}}}
,
a
c
≡
b
c
(
mod
n
)
{\displaystyle ac\equiv bc{\pmod {n}}}
.
Eulers
φ
{\displaystyle \varphi }
-funktion
Definition:
φ
(
n
)
{\displaystyle \varphi (n)}
är antalet positiva tal
d
≤
n
:
(
d
,
n
)
=
1
{\displaystyle d\leq n:(d,n)=1}
.
Definition: En funktion
f
{\displaystyle f}
som uppfyller
(
m
,
n
)
=
1
⇒
f
(
m
n
)
=
f
(
m
)
f
(
n
)
{\displaystyle (m,n)=1\Rightarrow f(mn)=f(m)f(n)}
säges vara multiplikativ .
Sats:
φ
{\displaystyle \varphi }
är multiplikativ.
Bevis: Bland talen
1
,
…
,
m
{\displaystyle 1,\ldots ,m}
finns exakt
φ
(
m
)
{\displaystyle \varphi (m)}
tal relativt prima till
m
{\displaystyle m}
, enligt definitionen av
φ
{\displaystyle \varphi }
.
Bland talen
1
+
k
m
,
…
,
m
+
k
m
{\displaystyle 1+km,\ldots ,m+km}
finns lika många, dvs
φ
(
m
)
{\displaystyle \varphi (m)}
, tal relativt prima till
m
{\displaystyle m}
, eftersom
(
m
,
t
)
=
(
m
,
t
+
k
m
)
{\displaystyle (m,t)=(m,t+km)}
. Det följer att antalet tal relativt prima till
m
{\displaystyle m}
bland talen
1
,
…
,
m
,
m
+
1
,
…
2
m
,
…
,
(
n
−
1
)
m
+
1
,
…
,
m
n
{\displaystyle 1,\ldots ,m,m+1,\ldots 2m,\ldots ,(n-1)m+1,\ldots ,mn}
, dvs talen mindre än
m
{\displaystyle m}
, är
m
⋅
n
{\displaystyle m\cdot n}
.
Sats:
p
{\displaystyle p}
primtal.
φ
(
p
α
)
=
p
α
−
p
α
−
1
{\displaystyle \varphi (p^{\alpha })=p^{\alpha }-p^{\alpha -1}}
. Bevis: De enda positiva talen mindre än
p
α
{\displaystyle p^{\alpha }}
som ej är relativt prima med
p
α
{\displaystyle p^{\alpha }}
är multipler
k
p
{\displaystyle kp}
av
p
{\displaystyle p}
.
k
{\displaystyle k}
kan anta
p
α
−
1
{\displaystyle p^{\alpha -1}}
olika värden då
0
<
k
p
≤
p
α
{\displaystyle 0<kp\leq p^{\alpha }}
. Det följer att
φ
(
p
α
)
=
p
α
−
p
α
−
1
{\displaystyle \varphi (p^{\alpha })=p^{\alpha }-p^{\alpha -1}}
.
φ
(
n
)
=
φ
(
p
0
α
0
…
p
n
α
n
)
=
φ
(
p
0
α
0
)
…
φ
(
p
n
α
n
)
=
p
0
α
0
(
1
−
1
p
0
)
…
p
n
α
n
(
1
−
1
p
n
)
=
p
0
α
0
…
p
n
α
n
(
1
−
1
p
0
)
…
(
1
−
1
p
n
)
=
n
∏
i
=
0
n
(
1
−
1
p
i
)
{\displaystyle \varphi (n)=\varphi (p_{0}^{\alpha _{0}}\ldots p_{n}^{\alpha _{n}})=\varphi (p_{0}^{\alpha _{0}})\ldots \varphi (p_{n}^{\alpha _{n}})=p_{0}^{\alpha _{0}}\left(1-{1 \over p_{0}}\right)\ldots p_{n}^{\alpha _{n}}\left(1-{1 \over p_{n}}\right)=p_{0}^{\alpha _{0}}\ldots p_{n}^{\alpha _{n}}\left(1-{1 \over p_{0}}\right)\ldots \left(1-{1 \over p_{n}}\right)=n\prod _{i=0}^{n}\left(1-{1 \over p_{i}}\right)}
.
Exempel på multiplikativa funktioner
τ
(
n
)
{\displaystyle \tau (n)}
- antalet positiva delare till
n
{\displaystyle n}
.
σ
(
n
)
{\displaystyle \sigma (n)}
- summan av de positiva delarna till
n
{\displaystyle n}
.
Möbius inversionformel
Definition: Låt
f
{\displaystyle f}
och
g
{\displaystyle g}
vara multiplikativa.
f
∗
g
:=
∑
d
|
n
f
(
d
)
f
(
n
d
)
{\displaystyle f*g:=\sum _{d|n}f(d)f\left({n \over d}\right)}
.
Definition: Möbiusfunktionen definieras som
μ
:=
{
1
⇐
n
=
1
(
−
1
)
n
⇐
n
=
p
1
…
p
n
0
a
n
n
a
r
s
{\displaystyle \mu :=\left\{{\begin{array}{c}1\Leftarrow n=1\\(-1)^{n}\Leftarrow n=p_{1}\ldots p_{n}\\0annars\end{array}}\right.}
.
Möbius inversionsformel:
F
=
f
∗
1
⇒
f
=
F
∗
μ
{\displaystyle F=f*1\Rightarrow f=F*\mu }
.