5. Moduloräkning

Exempel 1: Klockan är nu 21:00. Om 11 timmar börjar lektionen. Vad är klockan då?
Svaret på den frågan är inte 21+11=32 utan snarare 21+11-24=8. Då klockan passerar 23:59:59 börjar vi om på noll igen. Tiden på en klocka är egentligen resten vid heltalsdivision med 24; vi har att


När man bara intresserar sig för resterna och inte bryr sig om kvoten, pratar man om moduloräkning. Då man räknar med resterna vid division med heltalet n säger man att man räknar modulo n eller att man räknar i Zn. Två tal som har samma rest vid division med heltalet n kallar man ekvivalenta modulo n. Till exempel har vi att


eftersom


Att talen 25, 11, -3 och 4 är ekvivalenta modulo n kan vi beteckna med att de tillhör samma ekvivalensklass [4]7, kallad restklass 4 modulo 7. Restklasserna modulo 7 är mängderna


Vi ser att restklasserna utgör en partition av mängden av alla heltal Z, eftersom restklasserna är inbördes disjunkta samtidigt som unionen av dem är hela Z.
Exempel 2: Addera 34 och 51 modulo 7. Vi kan antingen beräkna summan direkt


eller stegvis


eftersom 85=7*12+1, 34=7*4+6 och 51=7*7+2.

Exempel 3: Beräkna 34  gånger 51 modulo 7.  Vi kan antingen beräkna produkten direkt


eller stegvis


eftersom 1734=7*247+5, 34=7*4+6 och 51=7*7+2.

Exempel 4: Beräkna inversen till 3 i modulo 7. Inversen till ett tal a är ett tal b=a-1 sådant att produkten ab=1. Låt oss bilda en tabell över produkterna modulo 7 mellan heltalen 0-6. Vi har

*
0
1
2
3
4
5
6
0
0
0
0
0
0
0
0
1
0
1
2
3
4
5
6
2
0
2
4
6
1
3
5
3
0
3
6
2
5
1
4
4
0
4
1
5
2
6
3
5
0
5
3
1
6
4
2
6
0
6
5
4
3
2
1

Vi ser från tabellen att 3-1 är 5, eftersom


Exempel 5: Beräkna inversen till 3 modulo 6. Vi bildar en liknande tabell som i exemplet ovan. Vi har

*
0
1
2
3
4
5
0
0
0
0
0
0
0
1
0
1
2
3
4
5
2
0
2
4
0
2
4
3
0
3
0
3
0
3
4
0
4
2
0
4
2
5
0
5
4
3
2
1

I det här fallet saknas invers till 3 eftersom det inte finns något tal som ger produkten 1 (modulo 6) vid multiplikation med 3.

Exempel 6: Lös ekvationen

Det är detsamma som att säga att

för något heltal m. Om vi sätter m=-x får vi den diofantiska ekvationen

som vi löst i exempel 1 i stycke 4. Lösningen till den diofantiska ekvationen är y=-468-97k, k heltal. Det innebär att den sökta lösningen är y=17, eftersom det enbart finns en lösning y i intervallet 0-96 (för k=-4), det vill säga att


Exempel 7: Lös ekvationen

Det är detsamma som att säga att

för något heltal m. Om vi sätter m=-x får den vi diofantiska ekvationen

som saknade lösning i exempel 2 i stycke 4. Det innbär att lösning även saknas till den här ekvationen.

Exempel 8: Lös ekvationen

Det är detsamma som att säga att

för något heltal m. Om vi sätter m=-x får den diofantiska ekvationen

som vi löst i exempel 1 i stycke 4. Lösningen till den diofantiska ekvationen är y=6-14k, k heltal. Det innebär att vi har 7 lösningar (lika många som gcd(98,35)) i intervallet 0-97. De fås för k=0,-1,-2,...,-6 och är

Vi kan enkelt visa att dessa är lösningar genom att sätta in i ekvationen. Till exempel har vi att


Föregående stycke          Tillbaka till kapitel X: Diskret matematik           Nästa stycke