Hitta alla lösningar x till ekvationerna med modul

Om vi har en kongruensekvation $ax\equiv b\ \pmod{n}$ skulle vi ju gärna hitta en invers $a^{-1}$ modulo $n$ sådan att $a^{-1}\cdot a\equiv1\ \pmod{n}$ och därefter enkelt lösa ekvationen genom:

$ax\equiv b\ \pmod{n}$

$a^{-1}\cdot ax\equiv a^{-1}\cdot b\ \pmod{n}$

$x\equiv a^{-1}\cdot b\ \pmod{n}$

Det stora problemet med detta är att det inte alltid går att finna inversen $a^{-1}$ beroende på vilket $n$-värde vi har. Det är nämligen så att det bara går att finna en invers $a^{-1}$ modulo $n$ om $\gcd(a,n)=1$.

Om den största gemensamma delaren inte är $1$ får vi skriva om kongruensekvationen på formen:

$ax=b+n\cdot k$

där $k\in\mathbb{Z}$. Eftersom GCD inte är 1 finns det någon gemensam delare $d$ större än ett i både $a$ och $n$. Om vi delar båda led på denna största gemensamma delare $d$ får vi då:

$\dfrac{a}{d}\cdot x=\dfrac{b}{d}+\dfrac{n}{d}\cdot k$

Eftersom $d$ är delare till både $a$ och $n$ är det säkert att $a/d$ och $n/d$ blir heltal. Däremot är det inte säkert att $b/d$ är ett heltal. Om det inte är ett heltal har ekvationen inga lösningar (som med den andra ekvationen i ditt exempel).

Om $b/d$ å andra sidan är ett heltal kan vi omvandla ekvationen:

$\dfrac{a}{d}\cdot x=\dfrac{b}{d}+\dfrac{n}{d}\cdot k$

till kongruensekvationen:

$a/d\cdot x\equiv b/d\ \pmod{n/d}$

eftersom vi nu dividerat bort den största gemensamma delaren $d$ vet vi att $\gcd(a/d,n/d)=1$ och därmed går det att finna en invers till $a/d$ och på så sätt ta fram lösningarna.

AlvinB skrev:

Om vi har en kongruensekvation $ax\equiv b\ \pmod{n}$ skulle vi ju gärna hitta en invers $a^{-1}$ modulo $n$ sådan att $a^{-1}\cdot a\equiv1\ \pmod{n}$ och därefter enkelt lösa ekvationen genom:

$ax\equiv b\ \pmod{n}$

$a^{-1}\cdot ax\equiv a^{-1}\cdot b\ \pmod{n}$

$x\equiv a^{-1}\cdot b\ \pmod{n}$

Det stora problemet med detta är att det inte alltid går att finna inversen $a^{-1}$ beroende på vilket $n$-värde vi har. Det är nämligen så att det bara går att finna en invers $a^{-1}$ modulo $n$ om $\gcd(a,n)=1$.

Om den största gemensamma delaren inte är $1$ får vi skriva om kongruensekvationen på formen:

$ax=b+n\cdot k$

där $k\in\mathbb{Z}$. Eftersom GCD inte är 1 finns det någon gemensam delare $d$ större än ett i både $a$ och $n$. Om vi delar båda led på denna största gemensamma delare $d$ får vi då:

$\dfrac{a}{d}\cdot x=\dfrac{b}{d}+\dfrac{n}{d}\cdot k$

Eftersom $d$ är delare till både $a$ och $n$ är det säkert att $a/d$ och $n/d$ blir heltal. Däremot är det inte säkert att $b/d$ är ett heltal. Om det inte är ett heltal har ekvationen inga lösningar (som med den andra ekvationen i ditt exempel).

Om $b/d$ å andra sidan är ett heltal kan vi omvandla ekvationen:

$\dfrac{a}{d}\cdot x=\dfrac{b}{d}+\dfrac{n}{d}\cdot k$

till kongruensekvationen:

$a/d\cdot x\equiv b/d\ \pmod{n/d}$

eftersom vi nu dividerat bort den största gemensamma delaren $d$ vet vi att $\gcd(a/d,n/d)=1$ och därmed går det att finna en invers till $a/d$ och på så sätt ta fram lösningarna.

 Jaa okej, så lite Euikliders algoritm? och det gäller samma regler vid modolo inverser som matris division? 

Ja, det finns lite likheter med Euklides algoritm, men det här behöver vi faktiskt bara göra en gång ifall $\gcd(a,n)\neq1$ eftersom vi dividerar bort alla gemensamma faktorer på en gång när vi dividerar med största gemensamma delaren. I Euklides algoritm kan man ju behöver upprepa stegen många gånger.

Du har rätt i att det här med invers är lite likt vad man gör när man löser matrisekvationer. Om matrisen är inverterbar (d.v.s. determinanten är nollskild) multiplicerar vi med inversen i båda led, annars måste vi göra något annat (Gausselimination).

På liknande sätt är det här, om $a$ är inverterbart modulo $n$ (d.v.s. största gemensamma nämnaren är ett) multiplicerar vi med inversen i båda led, annars måste vi göra något lite krångligare (dividera med $\gcd(a,n)$). Dock skulle jag inte säga att reglerna är samma.

AlvinB skrev:

Ja, det finns lite likheter med Euklides algoritm, men det här behöver vi faktiskt bara göra en gång ifall $\gcd(a,n)\neq1$ eftersom vi dividerar bort alla gemensamma faktorer på en gång när vi dividerar med största gemensamma delaren. I Euklides algoritm kan man ju behöver upprepa stegen många gånger.

Du har rätt i att det här med invers är lite likt vad man gör när man löser matrisekvationer. Om matrisen är inverterbar (d.v.s. determinanten är nollskild) multiplicerar vi med inversen i båda led, annars måste vi göra något annat (Gausselimination).

På liknande sätt är det här, om $a$ är inverterbart modulo $n$ (d.v.s. största gemensamma nämnaren är ett) multiplicerar vi med inversen i båda led, annars måste vi göra något lite krångligare (dividera med $\gcd(a,n)$). Dock skulle jag inte säga att reglerna är samma.

 Tack så mkt