2024-10-16

Kongruensräkning

Oavsett val av $a\in \mathbb{Z}$ gäller:

$[a]+[0]=[a]$ (eftersom $[a]+[b]=[a+b]$)
$[a]\cdot [1]=[a]$ (eftersom $[a]\cdot [b]=[a\cdot b]$)

Identiteter

Operatorerna ovan är binära operatorer.

$[0]$ är identitet för $+$ på ${\mathbb{Z}}_n$
$[1]$ är identitet för $\cdot$ på ${\mathbb{Z}}_n$

Inverser

Addition

$[a]$ har invers $[-a]$ för addition.

Multiplikation

$[a]$ har ibland* invers $\left[\frac{1}{a}\right]$ för multiplikation.

*: $\frac{1}{a}$ är typiskt sätt inte i $\mathbb{Z}$, så vi måste lägga på kravet att $\frac{1}{a}\in \mathbb{Z}$.

Det här kan formuleras om som:
$\frac{1}{a}\in \mathbb{Z}⟺\mathrm{\exists }x\in \mathbb{Z}xa=1$

Om vi kan lösa $[a]\cdot [x]=[1]$ så finns det en invers.

$[a]\cdot [x]=[1]⟺ax\equiv 1\text{ mod }n$

$\mathrm{\exists }x:ax\equiv 1\text{ mod }n$
$⟺\mathrm{\exists }x:n\mid ax-1$
$⟺\mathrm{\exists }x\mathrm{\exists }k:ax-1=nk$
$⟺\mathrm{\exists }x\mathrm{\exists }k:ax-nk=1$

Lös den diofantiska ekvationen $ax-nk=1$

Enligt Sats 5.22 är ekvationen lösbar om $sgd(a,n)=1$

Är det entydigt?

Antag $ax\equiv 1\equiv ay\text{ mod }n$
Då gäller $x\equiv x(ay)\equiv (xa)y\equiv y\text{ mod }n$
$⟹$$x$ är unikt för modulo $n$

Har visat sats 5.43:

Hur hittar vi inverser i ${\mathbb{Z}}_n?$

Titta på den underliggande diofantiska ekvationen där $a$ och $n$ är givna:

Euklides utökade algoritm: Hitta $u,v$ sådanna att:

Det innebär att:

Då gäller $[u]=[a{]}^{-1}$

Exempel 1

Hitta invers till 4 i ${\mathbb{Z}}_9$

Vill $[a][a{]}^{-1}=[1]$

1. Kolla $sgd(a,n)=sgd(4,9)=1$
   $⟹$det finns en invers $[4{]}^{-1}$ i ${\mathbb{Z}}_9$.

2. Euklides algoritm:
   $9=4\cdot 2+1$
   $4=1\cdot 4+0$

   $1=9\cdot 1-4\cdot 2=9\cdot v+4\cdot u$

   $u,v$ ovan $u=-2$, $v=1$
   $⟹[4{]}^{-1}=[-2]$ i ${\mathbb{Z}}_9$

3. Kontrollera:
   $[4][-2]=[-8]=[1]$ (eftersom $-8\equiv 1\text{ mod }9$)

Exempel 2

Lös $4x\equiv 3\text{ mod }9$
$⟺[4][x]=[3]$ m.a.p. ${\mathbb{Z}}_9$

För att lösa den måste vi dela med 4, så vi får bara x i HL. Det är samma sak som att multiplicera med $[4{]}^{-1}=[-2]$ (m.a.p. ${\mathbb{Z}}_9$):

$x\equiv (-2)\cdot 4x\equiv (-2)\cdot 3\equiv -6\equiv 3\text{ mod }9$

$x\equiv 3\text{ mod }9$ är en lösning till $4x\equiv 3\text{ mod }9$

Kongruensekvationer

Tag ekvationen $4x\equiv 3\text{ mod }9$ har lösning $x\equiv 3\text{ mod }9$ ($[x]=[3]$)

När kan vi lösa $ax\equiv b\text{ mod }n$?

Som innan är det lösbart om:

$\mathrm{\exists }x:ax\equiv b\text{ mod }n⟺\mathrm{\exists }x:n\mid ax-b$
$⟺\mathrm{\exists }x\mathrm{\exists }k:ax-b=nk$
$⟺\mathrm{\exists }x\mathrm{\exists }k:ax-nk=b$
$⟺sgd(a,n)\mid b$

D.v.s. $ax\equiv b\text{ mod }n$ lösbar om $sgd(a,n)\mid b$

Exempel

Hitta lösningar till $6x\equiv 15\text{ mod }9$ (*)

$a=6,n=9,b=15$

$sgd(6,9)=3,3\mid 15⟹$det finns lösningar

Två sätt att lösa (*):

Som kongruensekvation

$6x\equiv 15\text{ mod }9$

Dela med $sgd(6,9)=3$:

$\left(\frac{6}{3}\right)x\equiv \frac{15}{3}\text{ mod }\frac{9}{3}$
$⟺2x\equiv 5\text{ mod }3$

Vi vill hitta $[-2{]}^{-1}$ i ${\mathbb{Z}}_3$ och multiplicera för att få $x$.

Invertera $2$ i ${\mathbb{Z}}_3$: $2\cdot 2\equiv 4\equiv 1\text{ mod }3$

$⟹[2{]}^{-1}=[2]⟹x\equiv 2\cdot 2_x\equiv 2\cdot 5\equiv 10\equiv 1\text{ mod }3$

$x\equiv 1\text{ mod }3$ en lösning

Som diofantisk ekvation

Uttryck (*) som $6x+9y=15$

Dela med $sgd(6,9)=3:$

$⟺2x+3y=5$

Hitta en lösning, t.ex. via 2024-10-09#Euklides algoritm

Tag $x=y=1$

$⟹\text{alla lösningar }(1-3n,1+2n),n\in \mathbb{Z}$

Vi bryr oss inte om $y$-termen $1+2n$ eftersom det endast berättar antalet cyklar.

$x\equiv 1\text{ mod }3$

Kinesiska restsatsen

Bevis

$\text{(I)}⟺x=a+mk,k\in \mathbb{Z}$

För att hitta $k$, sätt in i $(\text{II})$:

$a+mk\equiv b\text{ mod }n$
$⟺mk\equiv b-a\text{ mod }n$

$sgd(m,n)=1⟹\mathrm{\exists }r\in \mathbb{Z}:m\cdot r\equiv 1\text{ mod }n$

Den allmänna lösningen ges av:

$x=a+mk$
$=a+m(r(b-a)+ny)$
$=a+mr(b-a)+mny$