Talteori Definition: Ett heltal
a
{\displaystyle a}
delbart med ett heltal
b
{\displaystyle b}
k
{\displaystyle k}
a
=
b
⋅
k
{\displaystyle a=b\cdot k}
∃
k
:
a
=
b
⋅
k
{\displaystyle \exists k:a=b\cdot k}
a
|
b
{\displaystyle a|b}
delar b. b är en delare till a.
Definition: En äkta delare till ett tal
a
{\displaystyle a}
d
∉
{
1
,
p
}
:
d
|
a
{\displaystyle d\notin \{1,p\}:d|a}
Notation: Den största gemensamma delaren till
a
{\displaystyle a}
b
{\displaystyle b}
(
a
,
b
)
{\displaystyle (a,b)}
Kongruenser Definition:
a
≡
b
(
mod
n
)
{\displaystyle a\equiv b{\pmod {n}}}
n
|
(
b
−
a
)
{\displaystyle n|(b-a)}
Sats: Om
a
≡
b
(
mod
n
)
{\displaystyle a\equiv b{\pmod {n}}}
c
{\displaystyle c}
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 }
Definition:
φ
(
n
)
{\displaystyle \varphi (n)}
d
≤
n
:
(
d
,
n
)
=
1
{\displaystyle d\leq n:(d,n)=1}
Definition: En funktion
f
{\displaystyle f}
(
m
,
n
)
=
1
⇒
f
(
m
n
)
=
f
(
m
)
f
(
n
)
{\displaystyle (m,n)=1\Rightarrow f(mn)=f(m)f(n)}
multiplikativ .
Sats:
φ
{\displaystyle \varphi }
1
,
…
,
m
{\displaystyle 1,\ldots ,m}
φ
(
m
)
{\displaystyle \varphi (m)}
m
{\displaystyle m}
φ
{\displaystyle \varphi }
1
+
k
m
,
…
,
m
+
k
m
{\displaystyle 1+km,\ldots ,m+km}
φ
(
m
)
{\displaystyle \varphi (m)}
m
{\displaystyle m}
(
m
,
t
)
=
(
m
,
t
+
k
m
)
{\displaystyle (m,t)=(m,t+km)}
m
{\displaystyle m}
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}
m
{\displaystyle m}
m
⋅
n
{\displaystyle m\cdot n}
Sats:
p
{\displaystyle p}
φ
(
p
α
)
=
p
α
−
p
α
−
1
{\displaystyle \varphi (p^{\alpha })=p^{\alpha }-p^{\alpha -1}}
p
α
{\displaystyle p^{\alpha }}
p
α
{\displaystyle p^{\alpha }}
k
p
{\displaystyle kp}
p
{\displaystyle p}
k
{\displaystyle k}
p
α
−
1
{\displaystyle p^{\alpha -1}}
0
<
k
p
≤
p
α
{\displaystyle 0<kp\leq p^{\alpha }}
φ
(
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)}
n
{\displaystyle n}
σ
(
n
)
{\displaystyle \sigma (n)}
n
{\displaystyle n}
Möbius inversionformel Definition: Låt
f
{\displaystyle f}
g
{\displaystyle g}
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 }
