Invers modulo
Moderatorer: Aleks855, Gustav, Nebuchadnezzar, Janhaa, DennisChristensen, Emilga
Hei. Vi har akkurat begynt med kongruensregning på VGS, og jeg sliter litt med å forstå hva som egentlig menes med en invers modulo, og hvordan man finner den. Hvis noen kunne forklart dette på en så enkel som mulig måte så hadde det vært veldig fint. Takk for all hjelp!
Jeg regner med du mener hva f. eks $a$ sin invers er modulo $n$. Når vi leter etter en invers til $a$ modulo $n$ leter vi etter et tall $x \in \mathbb{Z}$ slik at $ax \equiv 1 \pmod{n}$. For eksempel er en invers til $2$ modulo $11$ lik $6$ fordi $2 \cdot 6 = 12 \equiv 1 \pmod{11}$. Naturligvis har et $a$ en invers modulo $n$ hvis og bare hvis $ax \equiv 1 \pmod{n}$ er løsbar. Dette er det samme som at $n \mid ax-1 \implies \exists y \in \mathbb{Z}:ny=ax-1 \implies ny-ax=1$. En lineær diofantisk likning på denne formen er løsbar hvis og bare hvis $\gcd(n,y) \mid 1$. Altså har $a$ en invers modulo $n$ hvis og bare hvis $\gcd(n,a) \mid 1$.
For å finne inversen må du altså løse $ny-ax=1$ med f. eks Euklids algoritme. Er du kjent med hvordan du løser slike type likninger?
For å finne inversen må du altså løse $ny-ax=1$ med f. eks Euklids algoritme. Er du kjent med hvordan du løser slike type likninger?