Matematik/Diskret matematik/Talteori

Talteori

Definition: Ett heltal $a$ säges vara delbart med ett heltal $b$ om det existerar ett tal $k$ s.a. $a=b\cdot k$ (vilket kompakt kan skrivas $\exists k:a=b\cdot k$). Detta skrives $a|b$. a delar b. b är en delare till a.

Definition: En äkta delare till ett tal $a$ är ett positivt heltal $d\notin \{1,p\}:d|a$.

Notation: Den största gemensamma delaren till $a$ och $b$ betecknas $(a,b)$.

Kongruenser

Definition: $a\equiv b{\pmod {n}}$ definieras som $n|(b-a)$.

Sats: Om $a\equiv b{\pmod {n}}$, $c$ heltal, så

$a+c\equiv b+c{\pmod {n}}$,

$ac\equiv bc{\pmod {n}}$.

Eulers $\varphi$-funktion

Definition: $\varphi (n)$ är antalet positiva tal $d\leq n:(d,n)=1$.

Definition: En funktion $f$ som uppfyller $(m,n)=1\Rightarrow f(mn)=f(m)f(n)$ säges vara multiplikativ.

Sats: $\varphi$ är multiplikativ. Bevis: Bland talen $1,\ldots ,m$ finns exakt $\varphi (m)$ tal relativt prima till $m$, enligt definitionen av $\varphi$. Bland talen $1+km,\ldots ,m+km$ finns lika många, dvs $\varphi (m)$, tal relativt prima till $m$, eftersom $(m,t)=(m,t+km)$. Det följer att antalet tal relativt prima till $m$ bland talen $1,\ldots ,m,m+1,\ldots 2m,\ldots ,(n-1)m+1,\ldots ,mn$, dvs talen mindre än $m$, är $m\cdot n$.

Sats: $p$ primtal. $\varphi (p^{\alpha })=p^{\alpha }-p^{\alpha -1}$. Bevis: De enda positiva talen mindre än $p^{\alpha }$ som ej är relativt prima med $p^{\alpha }$ är multipler $kp$ av $p$. $k$ kan anta $p^{\alpha -1}$ olika värden då $0<kp\leq p^{\alpha }$. Det följer att $\varphi (p^{\alpha })=p^{\alpha }-p^{\alpha -1}$.

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

$\tau (n)$ - antalet positiva delare till $n$. $\sigma (n)$ - summan av de positiva delarna till $n$.

Möbius inversionformel

Definition: Låt $f$ och $g$ vara multiplikativa. $f*g:=\sum _{d|n}f(d)f\left({n \over d}\right)$.

Definition: Möbiusfunktionen definieras som $\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\Rightarrow f=F*\mu$.