Vis kilden til Modulær aritmetikk

[[Fil:Clock group.svg|thumb|300px|right|Tidsregning på denne klokken bruker modulær aritmetikk da 9  + 4 ≡ 1 (mod 12)}.]]

'''Modulær aritmetikk''' er basert  på å telle 1,2,3 og så videre opp til et tall ''n'' hvor man starter med 1 igjen. Tallet ''n'' kalles [[modulus]] for denne tellemåten. Med denne endelige [[tallmengde]]n kan man utføre de fire vanlige regneoperasjonene som dermed definerer en ny [[aritmetikk]].

Ved bruk av en vanlig klokke utfører man ubevisst modulær [[addisjon]] og [[subtraksjon]] med modulus ''n'' = 12. Hvis klokken for eksempel viser 5, vil den vise 2 etter 9 timer. På tilsvarende vis ville den ha vist 8 hvis den hadde blitt avlest 9 timer tidligere. Med matematisk notasjon ville man uttrykke disse to fastsettelsene av tidspunktene som {{nowrap|5 + 9 ≡  2 (mod 12)}} og {{nowrap|5 - 9 ≡  8 (mod 12)}}. Det betyr at regneoperasjonene gjøres «modulo» tolv, det vil si med modulus 12. Modulær aritmetikk blir derfor noen ganger omtalt som «klokkearitmetikk».

For å angi alle timene i et helt [[døgn]] ville man på samme vis bruke en modulus ''n'' = 24 for å skille mellom timer om natten og om dagen. Den samme, modulære aritmetikken benyttes også når man angir antall  [[grad (vinkel)|grader]] i en [[vinkel]] hvor ''n'' = 360&deg; benyttes. 

Det var [[Carl Friedrich Gauss]] som etablerte modulær aritmetikk som en viktig del av moderne matematikk i sitt store verk ''Disquisitiones Arithmeticae'' på begynnelsen av 1800-tallet. Her undersøkte han grunnlaget for [[konstruksjon (geometri)|konstruksjon]] av [[regulær mangekant|regulære mangekanter]]. Slike polygoner har samme geometri eller symmetri som en klokke.  I vår tid benyttes modulær aritmetikk innen [[informatikk]] som en bestanddel av de viktigste [[programmeringsspråk]]ene og spiller en sentral rolle i moderne [[kryptografi]]. Dessuten inngår den ved bestemmelsen av [[kontrollsiffer]] i [[personnummer]] samt sjekking av tallene som inngår i [[ISBN]]- og [[IBAN]]-systemene.

==Heltallsdivisjon==

Når man er gitt en viss [[modulus]] ''n'', kan man for hvert annet [[heltall]] ''x'' dele dette med ''n'' ved bruk av [[Divisjon (matematikk)#Heltallsdivisjon|heltallsdivisjon]]. Resultatet gir da vanligvis en rest ''r'' slik at resultatet kan skrives som

: <math> x = na + r </math>

hvor heltallet ''a'' er [[kvotient]]en. Resten bestemmes slik at den oppfyller 0 &le; ''r'' < ''n''. Hvis for eksempel ''n'' = 6 og ''x'' = 17, så er 17 = 6&sdot;2 + 5 slik at resten {{nowrap|''r'' {{=}} 5}}. Når resten er null, sier man at divisjonen «går opp». Da er ''n'' en [[faktor]] av ''x''.<ref name = RA> J. Reed og J. Aarnes, ''Matematikk i vår tid'', Universitetsforlaget, Oslo (1967).</ref>

I modulær aritmetikk omtaler man resultatet av denne divisjonen som at 17 er 5 [[modulo]] 6. Det skrives som 17 mod 6 = 5. I det generelle tilfellet har man da at

: <math> x \bmod  n = r </math>

Hvis dividenden ''x'' økes med et helt antall ''m'' av modulusen, vil ikke resten forandres. Derfor har man at

: <math> (x + m\cdot n) \bmod  n =  x \bmod  n </math>

hvor heltallet ''m'' også kan være negativt. For eksempel  er -13 mod 5 = (2 - 3&sdot;5) mod 5 = 2.

For å beregne summen ''x'' + ''y'' modulo ''n'' kan man benytte uttrykket

: <math> (x + y) \bmod  n = (x \bmod  n + y \bmod  n) \bmod  n </math>

Det følger fra å skrive ''x'' = ''na'' + ''r'' og ''y'' = ''nb'' + ''s'' der ''r'' = ''x'' mod ''n'' og ''s'' = ''y'' mod ''n''. Da blir (''x'' + ''y'') mod ''n'' = (''r'' + ''s'') mod ''n'' som gir formelen. Slik kan også beregningen av produktet ''xy'' mod ''n'' gjøres enklere når tallen ''x'' og ''y'' er spesielt store.<ref name = Silverman> J.H. Silverman, ''A Friendly Introduction to Number Theory'', Pearson Education, New Jersey (2011). ISBN 0-321-81619-6.</ref>

===Potenser===

En [[potens (matematikk)|potens]] av et tall  kan bli veldig stor når eksponenten blir stor og vil da være krevende å regne ut. Men med modulær aritmetikk kan ikke resultatet bli større enn modulus og beregningen er enklere.  Man kan da benytte at

: <math> x^m  \bmod  n = (x  \bmod  n )^m  \bmod  n </math>

som følger fra å skrive ''x'' = ''an'' + ''r&thinsp;'' slik at ''x'' mod ''n'' = ''r''. Ved bruk av [[binomialformel]]en for ''x''<sup>''m''</sup> vil da kun leddet ''r''<sup>''m''</sup> bidra  da alle andre ledd inneholder ''n'' som faktor.  Derfor blir også

: <math> (xy)^m = (x  \bmod  n)^m \cdot (y  \bmod  n)^m \bmod  n </math>

Dette kan illustreres ved å regne ut for eksempel 5<sup>9</sup> mod 7. Man kan da benytte at 5<sup>2</sup> mod 7 = 25 mod 7 = 4 slik at

: <math> 5^4  \bmod  7 = (5^2 \bmod  7)\cdot (5^2 \bmod  7) \bmod  7 = (4\cdot 4) \bmod  7 = 2 </math>

Nå er 5<sup>9</sup> = 5<sup>1 + 4 + 4 </sup>&thinsp; slik at man har

: <math> 5^9  \bmod  7 = 5\cdot 2\cdot 2 \bmod  7 = 20  \bmod  7 = 6 </math>

På denne måten kan beregning av høye potenser betraktelig forenkles.<ref name = Silverman/>

==Aritmetiske kongruenser==

To heltall ''x'' og ''y'' som gir den samme resten ''r'' når de divideres med ''n'', sier å være kongruente med hverandre modulo ''n''. Det skrives som 

: <math> x \equiv y \pmod n </math>

Her virker nå modulo-operasjonen på begge sider av ekvivalenstegnet.  Det betyr at ''x'' = ''an'' + ''r''&thinsp;  og ''y'' = ''bn'' + ''r''&thinsp; hvor ''a'' og ''b'' igjen er heltall. Resten oppfyller 0 &le; ''r'' < ''n''. To tall er dermed kongruente når deres differens kan deles med modulus ''n''. Denne egenskapen kan derfor også defineres ved at {{nowrap|(''x - y'') mod ''n'' {{=}} 0}} som betyr at ''x'' mod ''n'' = ''y'' mod ''n''. Hvis tallene ikke er kongruente med hverandre, sies de å være «inkongruente» for denne modulusen.<ref name = CR> R. Courant and H. Robbins, ''What is Mathematics: An Elementary Approach to Ideas and Methods'', Oxford University Press, Oxford (1996). ISBN 978-0-19-510519-3.</ref>

Som en eksempel kan man betrakte tallene 5 og 11. Med modulus ''n'' = 3 er 5 mod 3 = 2 og 11 mod 3 = 2. Derfor er  5  ≡  11 (mod 3) slik at de er kongruente. Derimot modulo 4 er de to tallene inkongruente med hverandre.

Fra definisjonen følger at kongruenser modulo ett og samme tall kan legges til og trekkes fra hverandre. De kan også multipliseres sammen som om de skulle være vanlige likheter. Det betyr at hvis ''a'' ≡ ''b'' (mod ''n'') og ''c'' ≡ ''d'' (mod ''n''), så er

: <math> a \pm c  \equiv b \pm d \pmod n , \;\;\;   ac  \equiv bd \pmod n </math>

Hver side av en kongruens kan multipliseres med samme tall. Man kan også dividere hver side med samme tall forutsatt at dette tallet er [[relativt primisk]] med modulusen.

===Eksempel===

Hvis modulus ''n'' = 5 og man betrakter de to tallene 13 og 16, så er deres sum modulo 5

: <math>13 + 16 = 29 \equiv 4 \pmod 5  </math>

Når addendene er store, kan man  først redusere dem ved å benytte at 13 ≡ 3 (mod 5) og 16 ≡ 1 (mod 5) slik at 13 + 16  ≡  3 + 1 (mod 5) = 4.

Betrakter man istedet produktet av disse to tallene, er

: <math>13 \times 16 = 208 \equiv 3 \pmod 5 </math>

Men dette resultatet kommer også frem ved å ta produktet mellom de kongruente tallene, 13&sdot;16  ≡  3&sdot;1 (mod 5) = 3.

Ved divisjon må man være mer påpasselig. Selv om 45 ≡ 15 (mod 10), så er 9 inkongruent med 3 modulo 10. Derimot er 46  ≡ 18 (mod 7) som betyr at 23 ≡ 9 (mod 7) når man dividerer kongruensen med 2 på begge sider. Det er tillatt når denne faktoren er primisk med modulusen.

==Kongruensklasser==

Kongruens mellom to tall er en [[ekvivalensrelasjon]] for en gitt modulus som gjør det mulig å dele alle [[heltall]]ene '''Z''' opp i ekvivalente klasser. Disse kalles da vanligvis for ''kongruensklasser'' eller '''restklasser'''. 

Hvis ''n'' er modulus, betegner (''n'') eller ''n''&thinsp;'''Z''' den klassen som inneholder tallene

: <math> (n) = \{0, \pm n, \pm 2n, \pm 3n, \cdots \} </math>

De er alle kongruente med tallet 0. Tilsvarende vil alle tallene som er kongruente med tallet ''a'', tilhøre kongruensklassen (''n'') + ''a''. Man vil dermed få ''n'' forskjellige klasser representert ved tallene {0, 1, 2, 3, .. , ''n'' - 1}.

Hver slik konkruensklasse kan nå betraktes som et nytt, matematisk objekt og kan betegnes ved det tallet som representerer det. Når for eksempel ''n'' = 3, har man de tre klassene '''0''', '''1''' og '''2'''. De kan kombineres ved addisjon ved at et representativt tall fra hver klasse adderes modulo ''n''. Med ''n'' = 3 vil da '''1''' + '''1''' = '''2''' og '''1''' + '''2''' = '''0'''. Klassene utgjør derfor en [[abelsk gruppe]] under addisjon hvor klassen '''0''' = (''n'') er enhetselementet. De danner på denne måten [[Gruppeteori#Faktorgrupper|faktorgruppen]] '''Z'''/(''n'') =  '''Z'''/''n''&thinsp;'''Z'''. Ofte skrives dette mer kompakt som '''Z'''<sub>''n''</sub> da restklassene også er en [[syklisk gruppe]] med ''n'' element.<ref name = RA/>

===Enheter og nulldivisorer===

Man kan også multiplisere sammen kongruensklasser ved å modulært multiplisere representanter for hver av klassene. For eksempel når modulus ''n'' = 6, blir

: <math> \mathbf{4}\cdot \mathbf{5} = \mathbf{2}, \;\;\; \mathbf{5}\cdot \mathbf{5} = \mathbf{1} </math>

Under multiplikasjon utgjør derfor alle restklassene en matematisk [[ring (matematikk)|ring]] med '''1''' = (''n'') + 1 som enhetselement. Den inneholder ''n''&thinsp; element og kan bli oppdelt i ''enheter'' og [[nulldivisor]]er. En enhet er definert ved å ha en invers. Det betyr at den er [[relativt primisk]] til modulus ''n''. Deres antall er derfor gitt ved [[Eulers totientfunksjon]] ''&phi;''(''n''). Resten av elementene er nulldivisorer.<ref name = MLB>S. MacLane and G. Birkhoff, ''Algebra'', MacMillan Publishing Co., New York (1979). ISBN 0-02-978830-7.</ref> 

For eksempel, for ''n'' = 6 er '''1''' og '''5''' enheter, mens '''0''', '''2''', '''3''', '''4''' er nulldivisorer. Det kan man se fra at '''2'''&sdot;'''3''' = '''3'''&sdot;'''4''' = '''0'''. På samme måte inneholder '''Z'''<sub>12</sub> enhetene '''1''', '''5''', '''7''' og '''11'''. De resterende 8 elementene er nulldivisorer. Produktet av to enheter er en ny enhet illustrert ved '''5'''&sdot;'''7''' = '''11''' i '''Z'''<sub>12</sub>. Sammen danner de en [[abelsk gruppe]] som kalles '''enhetsgruppen''' og betegnes ('''Z'''/''n'''''Z''')<sup>&times;</sup> med ''&phi;''(''n'') element. 

I det spesielle tilfelle at modulus er et [[primtall]] ''p'', er '''0''' den eneste nulldivisor i ringen. Da har hvert element '''a''' en multiplikativ invers '''a'''<sup>-1</sup> = '''1'''/'''a''' som oppfyller at '''a'''&sdot;'''a'''<sup>-1</sup> = '''1'''. I såfall går ringen '''Z'''/''p'''''Z''' over til å bli en endelig [[kropp (matematikk)|tallkropp]] og betegnes som '''F'''<sub>''p''</sub> eller GF(''p''). Velger man for eksempel  ''p'' = 7, er '''2'''&sdot;'''4''' = '''1''' slik at '''2'''<sup>-1</sup> = '''1'''/'''2''' = '''4''' og derfor '''3'''/'''2''' = '''3'''&sdot;'''4''' = '''5'''. Videre er '''1'''/'''3''' = '''5''' slik at '''1'''/'''5''' = '''3''', mens '''6''' er sin egen invers da '''6'''&sdot;'''6''' = '''1'''.
Slike [[endelig kropp|tallkropper]] er av stor betydningen innen [[kryptografi]].<ref name = AG> A. Ash and R. Gross, ''Fearless Symmetry: Exposing the Hidden Patterns of Numbers'', Princeton University Press, New Jersey (2006). ISBN 0-691-12492-2.</ref>

===Fermats lille teorem===

Den endelige tallkroppen '''F'''<sub>''p''</sub>  inneholder ''p'' element. Ser man bort fra elementet '''0''', danner de resterende ''p'' - 1&thinsp; elementene en endelig [[gruppe (matematikk)|gruppe]] hvor elementene kombineres ved multiplikasjon og har '''1''' som enhetselement. Denne betegnes vanligvis som  ('''F'''<sub>''p''</sub>)<sup>&times;</sup> eller GF<sup>&times;</sup>(''p'').<ref name = AG/>

Hvis man betrakter et element '''a''', vil det gi ''p'' - 1 forskjellige element når det multipliseres med seg selv. Tilsammen utgjør de en [[syklisk gruppe]]. Dette kan illustereres for ''p'' = 5 ved å betrakte for eksempel elementet '''2'''. Da er '''2'''&sdot;'''2''' = '''2'''<sup>2</sup> = '''4''',  '''2'''<sup>3</sup> = '''4'''&sdot;'''2''' = '''3''',  '''2'''<sup>4</sup> = '''3'''&sdot;'''2''' = '''1'''. Hadde man i stedet valgt '''a''' = '''3''' eller '''4''', ville igjen '''3'''<sup>4</sup> =  '''4'''<sup>4</sup> = '''1'''. Dette skjer alltid når ''p'' er et primtall slik at gruppen blir syklisk. 

Generelt kan man da betrakte et vilkårlig element '''a''' i gruppen med en viss orden ''k''. Denne er definert ved at '''a'''<sup>''k''</sup> = '''1'''. Ifølge [[Gruppeteori#Lagranges teorem og faktorgrupper|Lagranges teorem]] er dette tallet ''k'' en faktor i det totale antall gruppeelement. Det betyr at ''p'' - 1 = ''k&thinsp;m'' hvor ''m'' et et eller annet heltall. Dermed har man med en gang at

: <math> \mathbf{a}^{p-1} =   \mathbf{a}^{km} = \mathbf{1} </math>

Det representative tallet ''a'' i konjugasjonsklassen oppfyller derfor

: <math> a^{p-1} \equiv 1 \pmod p </math>

der ''a'' ikke skal være delbar med ''p''. For eksempel med ''p'' = 7 er 2<sup>6</sup> = 64 ≡ 1 mod 7. Dette er [[Fermats lille teorem]] som har stor betydning i [[tallteori]].<ref name = RA/>

==Wilsons teorem==

John Wilson var student ved [[Universitetet i Cambridge]] rundt år 1770 da en formulerte et nytt teorem i modulær aritmetikk. Det ble bevist av [[Joseph-Louis Lagrange|Lagrange]] noen få år senere og gjelder når modulus ''p'' er et primtall. Da er

: <math> (p - 1)! \equiv -1 \pmod p </math>

når det uttrykkes ved [[Fakultet (matematikk)|fakultetsfunksjonen]] ''n''! = 1&sdot;2&sdot;3&sdot;...&sdot;''n''. Alternativt kan man si at (''p'' - 1)! + 1 er delelig med ''p'' når ''p'' er et primtall. Har man for eksempel ''p'' = 5, så finner man 4! = 24. Nå er 24 + 1 = 25 som er deilig med 5 i overensstemmelse med teoremet.<ref name = Ore> O. Ore, ''Number Theory and its History'', Dover Publications, New York (1988). ISBN 0-486-65620-9.</ref>

Et enkelt bevis kan baseres på at restklassene {'''1''', '''2''', '''3''', ... , '''p-1'''} er elementer i gruppen ('''F'''<sub>''p''</sub>)<sup>&times;</sup>. Da hvert element '''a''' av disse har sin egen invers '''a'''<sup>-1</sup>, kan produktet '''2'''&sdot;'''3'''&sdot; ... &sdot;'''p - 2''' omskrives som (''p'' - 3)/2 produkt av delprodukt på formen  '''a'''&sdot;'''a'''<sup>-1</sup> = '''1''' som dermed også blir verdien til hele produktet. Resultatet er da

: <math> \mathbf{1}\cdot \mathbf{2}\cdot \mathbf{3}\cdots (\mathbf{p -2})\cdot(\mathbf{p -1}) = \mathbf{p -1} </math>

hvor ''p'' - 1 ≡  -1 (mod ''p'') som gir innholdet av teoremet.

Som en konkret illustrasjon av denne argumentasjonen, kan man betrakte ''p'' = 11. Da finner man ved direkte utregning de inverse elementene '''2'''<sup>-1</sup> = '''6''', '''3'''<sup>-1</sup> = '''4''', '''5'''<sup>-1</sup> = '''9''' og '''7'''<sup>-1</sup> = '''8''' slik at 

: <math>10! = 1(2 \cdot 6)(3 \cdot 4)(5 \cdot 9)(7 \cdot 8)10  \equiv -1\ (\mbox{mod}\ 11) </math>

På lignende måte kan man bevise at for en ikke-primisk modulus ''n'' > 4 vil (''n'' - 1)! ≡ 0 (mod ''n''). I det spesielle tilfellet  at ''n'' = 4, blir 3! = 6  ≡ 2 (mod 4). Rent praktisk betyr dette at hvis (''n'' - 1)! er delelig med ''n'' > 4, så er ''n'' et sammensatt tall.<ref name = Ore/>

===Alternativt bevis===

Wilsons teorem følger også ganske direkte fra Fermats lille teorem. Det sier at ligningen

: <math> x^{p-1} - 1 \equiv 0 \pmod p </math>

er oppfylt for alle  <math> x = \{1, 2, 3, ... , p - 1\} </math>. Fra [[algebraens fundamentalteorem]] følger da at man må ha sammenhengen

: <math> x^{p-1} - 1 \equiv ( x -1)(x -2) (x-3) \cdots (x - p+1) \pmod p </math>

Ved å sette ''x'' = ''p'' vil produktet på høyre side bli (''p'' - 1)!. På venstre side vil man stå igjen med -1 da ''p''<sup>&thinsp;''p'' - 1</sup> er null modulo ''p''.

==Primitive røtter==

Hvert element ''a'' i enhetsgruppen  ('''Z'''/''n'''''Z''')<sup>&times;</sup> er relativt primisk med modulus ''n'', det vil si at [[største felles faktor]]  gcd(''a,n'') = 1. Det betyr at det totale antall element gruppen inneholder, er gitt ved [[Eulers totientfunksjon|totientfunksjonen]] ''&phi;''(''n''). Når ''n'' er et primtall, er ''&phi;''(''n'') = ''n'' - 1. Eulers teorem sier da at for hvert element ''a'' må man da ha at

: <math> a^{\phi(n)} \equiv 1 \pmod n </math>

Dette kravet vil generelt være oppfylt når ''a''<sup>''r''</sup> ≡ 1 (mod ''n'') der  heltallet ''r'' er en faktor i tallet ''&phi;''(''n''). Man sier da at elementet ''a'' har '''orden''' ''r&thinsp;'' for modulus ''n''. Elementet ''a'' = 1 har alltid orden ''r'' = 1 uavhengig av størrelsen til modulus. Alle element i gruppen som har den maksimale orden ''r''<sub>''max''</sub> =  ''&phi;''(''n''), kalles '''primitive røtter'''. Denne betegnelsen kommer fra tilsvarende løsninger av [[Regulær mangekant#Sirkeldelingsligningen|sirkeldelingsligningen]]. Hvert slikt element vil generere alle de andre elementene i gruppen ved at det multipliseres mange nok ganger med seg selv. Det kalles derfor også ofte for en «generator» og gruppen er [[syklisk gruppe|syklisk]].<ref name = Ore/>

Når ''n'' = 3, består gruppen av ''&phi;''(3) = 3 - 1 = 2 element som er {1, 2}. Nå er 2<sup>2</sup> = 4 ≡ 1 (mod 3) slik at 2 er en primitive rot. Likedan for ''n'' = 4 består gruppen av de to elementene 1 og 3 hvorav 3 er primitiv. For ''n'' = 5 inneholder gruppen ''&phi;''(5) = 5 - 1 = 4 element som er {1, 2, 3, 4}. I dette tilfelle er både 2 og 3 primitive røtter, men ikke 4 da  4<sup>2</sup> = 16 ≡ 1 (mod 5).  

Hvis ''g'' er en primitiv rot, vil den inverse

: <math> g^{-1} = g^{\phi(n) - 1}  \mod n </math>

også være en primitiv rot. For eksempel når ''n'' = 7, kan man sjekke at 3 er en primitiv rot. Det inverse elementet er 3<sup>-1</sup> = 3<sup>6 - 1</sup> mod 7 = 243 mod 7 = 5. Av de seks elementene {1, 2, 3, 4, 5, 6} er det bare 3 og 5 som er primitive for denne modulus. Når ''n'' = 8, er ingen av elementene {1, 3, 5, 7} primitive.

Primitive røtter finnes for alle moduli ''n'' = 2, 4, ''p''<sup>''k''</sup> og 2''p''<sup>''k''</sup> der primtallet ''p'' > 2 og ''k'' er et naturlig tall. Det finnes ingen systematisk fremgangsmåte for å identifisere de primitive røttene bortsett fra ved direkte utregning.<ref name = Schroeder> M.R. Schroeder, ''Number Theory in Science and Communication'', Springer-Verlag, Berlin (1984). ISBN 3-540-12164-1.</ref>

==Lineære kongruenser==

En eller flere [[polynom#Polynomligninger|polynomligning]] kan også løses innen rammen av modulær aritmetikk. De kalles da «kongruensrelasjoner» eller ganske enkelt for kongruenser. Avhengig av polynomenes grad, er de enkleste slike relasjoner lineære eller eventuelt kvadratiske kongruenser. I det spesielle tilfellet at modulus er et primtall ''p'', tilsvarer dette å finne  løsninger av ligningene innen [[endelig kropp|tallkroppen]] '''F'''<sub>''p''</sub> = '''Z'''/''p''&thinsp;'''Z'''.

Det enkleste tilfellet er en ligning med en ukjent. Den skrives som

: <math>ax \equiv c \pmod n </math>

hvor ''a'' og ''c'' er [[heltall]]. Denne relasjonen omtales som en ''lineær kongruens''. Eventuelle løsninger kan finnes fra den ekvivalente ligningen

: <math> ax + ny = c </math>

for ett eller flere heltall ''y''. Denne kongruensen er da ekvivalent med en [[diofantisk ligning]].

Løsningen av denne ligningen kan finnes ved bruk av [[Euklids algoritme]] og avhenger av den [[største felles divisor]] ''m'' = gcd(''a,n''). Når denne samtidig er en faktor i konstanten ''c'', så har kongruensen ''m'' inkongruente løsninger i intervallet {0, 1, 2, 3, ..., ''n'' - 1}. Hvis det derimot ikke er tilfelle, finnes det ingen løsninger.<ref name = Silverman/>

Som et eksempel kan man betrakte den lineære kongruensen

: <math> 4x  \equiv 6 \pmod {10} </math>

Her er ''m'' = gcd(4,10) = 2 som også er en faktor i ''c'' = 6. Derfor finnes det to løsninger som er ''x'' = 4 og ''x'' = 9. Hadde man istedet  her hatt ''c'' = 7, vil det ikke vært noen løsninger.

Når ''a'' og ''n'' er [[relativt primisk]]e, er ''m'' = 1 og kongruensen har bare en løsning. Det er tilfellet når modulus ''n'' = ''p'' er et primtall og den lineære kongruensen kan skrives som ligningen

: <math> \mathbf{a}\cdot\mathbf{x} = \mathbf{c}</math>

i tallkroppen '''F'''<sub>''p''</sub>. Løsningen er da formelt gitt som '''x''' = '''a'''<sup>-1</sup>&sdot;'''c'''. Har man for eksempel ''p'' = 7, er løsningen av 4''x'' ≡ 6 (mod 7) gitt ved ''x'' = 5 fordi '''4'''<sup>-1</sup> = '''2''' og '''2'''&sdot;'''6''' = '''5''' i '''F'''<sub>7</sub>. På samme vis finner man at 16''x'' ≡ 5 (mod 29) har løsningen ''x'' = 13. Når ''p'' er stor, er likevel fremgangsmåten med Euklids algoritme den raskeste.<ref name = Silverman/>

==Se også==

* [[Kvadratisk rest]]

==Referanser==
<references/>

==Eksterne lenker==

* E.W. Weisstein, [https://mathworld.wolfram.com/ModularArithmetic.html ''Modular Arithmetic''], Wolfram MathWorld
* [[Khan Academy]], [https://nb.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/what-is-modular-arithmetic ''An Introduction to Modular Math''], pedagogisk læreverk
* Encyclopediaofmath, [https://encyclopediaofmath.org/index.php?title=Congruence ''Congruence''], generell oversikt
* Cut-the-Knot, [https://www.cut-the-knot.org/blue/Modulo.shtml ''Modular Arithmetic''], spesielt om kongruensklasser

{{Autoritetsdata}}

[[Kategori:Aritmetikk]]
[[Kategori: Tallteori]]