Invers modulo

Her kan du stille spørsmål vedrørende problemer og oppgaver i matematikk for videregående skole og oppover på høyskolenivå. Alle som føler trangen er velkommen til å svare.

Moderatorer: Aleks855, Gustav, Nebuchadnezzar, Janhaa, DennisChristensen, Emilga

Svar
Gjest

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!
Markus
Fermat
Fermat
Innlegg: 767
Registrert: 20/09-2016 13:48
Sted: NTNU

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?
Gjest

Ja det er jeg. Tusen takk for utfyllende svar!
Svar