2024-10-17

Kongruensräkning

Kinesiska restsatsen

Om $x=x_0+mny,y\in \mathbb{Z}$

Exempel

Hitta minsta positiva lösningen till:

$$\{\begin{array}{l}x\equiv 12\text{ mod }31\\ x\equiv 20\text{ mod }41\end{array}$$

Lösning: $sgd(31,41)=1$

Från $x\equiv 12\text{ mod }31:x=12+31k,k\in \mathbb{Z}$
Sätt in i 2:a ekvationen:

$12+31k\equiv 20\text{ mod }41$
$⟺31k\equiv 8\text{ mod }41$

Hitta invers till $[31]$ i ${\mathbb{Z}}_{41}$ för att få $k$.

Eulers algoritm:
$41=31\cdot 1+10$
$31=10\cdot 3+1$
$10=1\cdot 10+0$

$1=31-3\cdot 10$
$=31-3(41-31)$
$=4\cdot 31-3\cdot 41$
$⟹4\cdot 31\equiv 1\text{ mod }41$
$⟹[31{]}^{-1}=[4]$ i ${\mathbb{Z}}_{41}$

Multiplicera med $[31{]}^{-1}$

$k\equiv 4\cdot 8\equiv 32\text{ mod }41$
$⟺k=32+41y,y\in \mathbb{Z}$

Sätt in i uttryck för $x$:

$x=12+31k$
$=12+31(32+41y)$
$=12+31\cdot 32+31\cdot 41y$
$=1004+1271y,y\in \mathbb{Z}$

Svar:
Minsta positiva lösning ges av $y=0$ ($x_0=1004$)

Förenkla kongruenser

Eulers $\mathrm{\Phi }$-funktion och sats

$\mathrm{\Phi }:{\mathbb{Z}}_{+}\to {\mathbb{Z}}_{+}$ definierat enligt följande:

$\mathrm{\Phi }(n)=|\{a\in \mathbb{Z}:1\le a\le n,sgd(a,n)=1\}|$
$=|x\in {\mathbb{Z}}_{+}:x\text{ är inverterbart}|$

Gäller att $\mathrm{\Phi }(1)=1,\mathrm{\Phi }(2)=1,\mathrm{\Phi }(3)=2,\mathrm{\Phi }(4)=2,\dots$

$\mathrm{\Phi }(p)=p-1$ där $p$ är ett primtal.

Betrakta $\mathrm{\Phi }(p^k),k\in {\mathbb{Z}}_{+}$

Låt $1\le a\le p^k-1$

$sgd(a,p^k)\ne 1$
$⟺p\mid a$
$⟺a\in \{p,2p,3p,\dots ,(p^{k-1})p\}$
$⟺\mathrm{\Phi }(p^k)=p^k-p^{k-1}=p^{k-1}(p-1)$