Teorija števil

Deljivost celih števil

Izrek o deljenju: Naj bosta $m,n\in \mathbb{Z}$ in $m>0$. Obstajata enolično določeni celi števili $k$ in $r$, pri čemer je:

$$n=k\ast m+r\text{ in velja }0\le r<m$$

• k … kvocient števil n in m: $k=[\frac{n}{m}]$
• r … ostanek pri deljenju števila n z m

Število $m$ deli število $n$: $m|n⟺n=x\ast m\in \mathbb{Z}$
Primeri: $0|0$, $\mathbb{N}|0$, $3|12$
Če števili $m,n$ nista enaki $0$, potem lahko definiramo:
Največji skupni delitelj števil $m,n$: $gcd(m,n)=max\{d\in \mathbb{Z};d|mind|n\}$
Najmanjši skupni večkratnik števil $m,n$: $lcm(m,n)=min\{v\in \mathbb{Z};m|vinn|vinv>0\}$

Števili $m,n$ sta si tuji: $a\perp b⟺gcd(a,b)=1$

• $a|(b\ast c)\wedge a\perp b⟹a|c$
• $a,b\in \mathbb{N}⟹gcd(a,b)\ast lcm(a,b)=a\ast b$

Razširjeni Evklidov algoritem (REA)

Iščemo $gcd(m,n)$ in koeficienta $s,t$
Izrek: $gcd(m,n)=r=s\ast m+t\ast n$

Primer postopka na roke:

1. $m,n$ naj bosta velikostno urejena ($m>n$)
2. Prvi dve vrstici (enačbi $I$ in $II$) sta predpisani s koeficienti $(1,0)$ in $(0,1)$
3. Nato izračunamo ostanek naslednje vrstice: $r_{i+1}=r_{i-1}mod{r}_i$
   Primer: $gcd(765,646)=?$
   
   Rezultat predzadnje vrstice ($17$) je $gcd$, pozitivni del vsote v zadnji vrstici ($29070$) pa je $lcm$

Koda algoritma:

int gcd(int m, int n, int & s, int & t) {
    if (m == 0) {
        s = 0;
        t = 1;
        return n;
    }
    int s1, t1;
    int d = gcd(n % m, m, s1, t1);
    s = t1 - (n / m) * s1;
    t = s1;
    return d;
}

Diofantske enačbe

Diofantska enačba: ima celoštevilske podatke in iščemo celoštevilske rešitve

Linearna diofantska enačba z dvema neznankama: enačba oblike $a\ast x+b\ast y=c$
Znani so $a,b,c\in \mathbb{Z}$ ($a,b$ … koeficienta enačbe, $c$ … desna stran), iščemo pa celoštevilsko rešitev $x,y$
Rešljiva je ntk. $gcd(a,b)|c$, sicer LDE nima rešitev

Naj par $x_0,y_0$ reši LDE $a\ast x+b\ast y=c$ in $d=gcd(a,b)$. Potem so:

$$\begin{array}{rl}{x}_t& =x_0+t\ast \frac{b}{d}\\ y_t& =y_0-t\ast \frac{a}{d}\end{array}$$

Primer: LDE $21x+9y=138$

Če linearno kombinacijo, ki vsebuje gcd, pomnožimo s $\frac{138}{3}$, pridelamo zvezo:

$$46\ast 21+(-92)\ast 9=138$$

s čimer dobimo $x_0=46$ in $y_0=-92$, kar je rešitev osnovne enačbe, s formulama za $x_t,y_t$ pa dobimo še ostale možne rešitve.

Praštevila

Praštevilo: naravno število $n>1$ z natanko dvema pozitivnima deliteljema
Praštevilska dvojčka: par oblike $(p,p+2)$

Klasičen evklidov izrek: Obstaja neskončno mnogo praštevil
Iz $p_1,...,p_n$ lahko zmeraj sestavimo novo praštevilo $p=p_1\ast ...\ast p_n+1$

Vsak $n\ge 2\in \mathbb{N}$ je deljivo s katerim od praštevil $⟹$
Enolični razcep: Vsak $n\ge 2\in \mathbb{N}$ lahko zapišemo kot produkt praštevil

Eulerjeva funkcija: $\phi (x)=|\{k\in \mathbb{N};1\le k\le n\wedge k\perp n\}|$ … število števil med $1$ in $n$, ki so tuja $n$

• $p$ je praštevilo $⟹\phi (p)=p-1$ oz. bolj splošno $\phi (p^n)=p^n-p^{n-1}$
• $a\perp b⟹\phi (a\ast b)=\phi (a)\ast \phi (b)$
  Naj bo $n\in \mathbb{N}$ in $n=p_1^{k_1}\ast ...\ast p_m^{k_m}$ njegov praštevilski razcep. Tedaj:

$$\phi (n)=(p_1^{k_1}-p_1^{k_1-1})\ast ...\ast (p_m^{k_m}-p_m^{k_m-1})=n\ast (1-\frac{1}{p_1})\ast ...\ast (1-\frac{1}{p_m})$$

Konguence

a mod b: ostanek $a$-ja pri deljenju z $m$
Kongruenca po modulu m: relacija $a\equiv b(\mathrm{mod}m)\sim m|(a-b)\sim a\mathrm{mod}m=b\mathrm{mod}m$

1. Kongruenca po modulu je ekvivalenčna relacija v $\mathbb{Z}$
2. Če $a\equiv b(\mathrm{mod}m)$, potem:

$$\begin{array}{rl}a\pm c& \equiv b\pm c(\mathrm{mod}m)\\ a\ast c& \equiv b\ast c(\mathrm{mod}m)\\ a^n& \equiv b^n(\mathrm{mod}m)\end{array}$$

3. Če $a\equiv b(\mathrm{mod}m)\wedge c\equiv d(\mathrm{mod}m)$, potem:

$$\begin{array}{rl}a\pm c& \equiv b\pm d(\mathrm{mod}m)\\ a\ast c& \equiv b\ast d(\mathrm{mod}m)\end{array}$$

4. Če $a\ast c\equiv b\ast c(\mathrm{mod}m)\wedge c\perp m$, potem:

$$a\equiv b(\mathrm{mod}m)$$

5. Če sta $p,q$ različni praštevili, potem:

$$a\equiv b(\mathrm{mod}p)\wedge a\equiv b(\mathrm{mod}q)⟺a\equiv b(\mathrm{mod}pq)$$

Eulerjev izrek

Izrek: Naj bo $a\in \mathbb{Z}$, $m\ge 2\in \mathbb{N}$, in $a\perp m$. Tedaj je:

$$a^{\phi (m)}\equiv 1(\mathrm{mod}m)$$

Mali fermatov izrek

Izrek: Če je $p$ praštevilo in $a\perp p$, potem je:

$$a^{p-1}\equiv 1(\mathrm{mod}p)$$

in za vse $a\in \mathbb{Z}$ velja:

$$a^p\equiv a(\mathrm{mod}p)$$