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 $\mathrm{\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(\mathrm{mod}n)$ definieras som $n|(b-a)$.

Sats: Om $a\equiv b(\mathrm{mod}n)$, $c$ heltal, så

$a+c\equiv b+c(\mathrm{mod}n)$,

$ac\equiv bc(\mathrm{mod}n)$.

Eulers $\phi$-funktion

Definition: $\phi (n)$ är antalet positiva tal $d\le 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: $\phi$ är multiplikativ. Bevis: Bland talen $1,\dots ,m$ finns exakt $\phi (m)$ tal relativt prima till $m$, enligt definitionen av $\phi$. Bland talen $1+km,\dots ,m+km$ finns lika många, dvs $\phi (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,\dots ,m,m+1,\dots 2m,\dots ,(n-1)m+1,\dots ,mn$, dvs talen mindre än $m$, är $m\cdot n$.

Sats: $p$ primtal. $\phi (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\le p^{\alpha }$. Det följer att $\phi (p^{\alpha })=p^{\alpha }-p^{\alpha -1}$.

$\phi (n)=\phi (p_0^{{\alpha }_0}\dots p_n^{{\alpha }_n})=\phi (p_0^{{\alpha }_0})\dots \phi (p_n^{{\alpha }_n})=p_0^{{\alpha }_0}(1-\frac{1}{p_0})\dots p_n^{{\alpha }_n}(1-\frac{1}{p_n})=p_0^{{\alpha }_0}\dots p_n^{{\alpha }_n}(1-\frac{1}{p_0})\dots (1-\frac{1}{p_n})=n\prod _{i=0}^n(1-\frac{1}{p_i})$.

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(\frac{n}{d}\right)$.

Definition: Möbiusfunktionen definieras som $\mu :=\{\begin{array}{c}1\Leftarrow n=1\\ (-1{)}^n\Leftarrow n=p_1\dots p_n\\ 0annars\end{array}$.

Möbius inversionsformel: $F=f*1\Rightarrow f=F*\mu$.