Modulo – räkna ut a mod n, potenser och inverser

Vad betyder modulo?

a mod n är resten när a delas med n. 17 mod 5 är 2, eftersom 5 går 3 gånger i 17 och det blir 2 över. Resten ligger alltid mellan 0 och n − 1. Begreppet hänger alltså tätt ihop med kvot och rest, men i modulär räkning är det bara resten som är intressant.

Tänk på en klocka. Efter 12 börjar den om på 1 (eller 0), så klockan räknar modulo 12. Är klockan 9 och det går 30 timmar visar den inte 39 utan 3, eftersom 39 mod 12 är 3. Det är därför modulär räkning kallas klockaritmetik. Kalkylatorn ritar en klocka med n steg och visar var resten hamnar.

Formeln

För heltal a och n ≠ 0 finns exakt ett par av kvot q och rest r så att

$a=n·q+r$, där $0\le r<\left|n\right|$.

Kvoten fås genom att dela och avrunda, nedåt om n > 0 och uppåt om n < 0, så att resten blir 0 eller större. Resten är det som blir kvar: r = a − n · q. Två tal som har samma rest modulo n kallas kongruenta, och man skriver till exempel 17 ≡ 2 (mod 5). Alla tal i följden … −8, −3, 2, 7, 12 … har resten 2 modulo 5.

Negativa tal

Med negativa tal finns två konventioner, och det är en vanlig källa till fel. Matematiskt väljs kvoten så att resten alltid blir positiv: −17 mod 5 är 3, eftersom −17 = 5 · (−4) + 3. Operatorn % i JavaScript och C avrundar i stället kvoten mot noll, och ger då −17 % 5 = −2. Python ger 3, precis som matematiken, eftersom resten där får samma tecken som n.

Ska resten användas som en position, till exempel en veckodag eller en plats i en lista, är det nästan alltid den positiva resten du vill ha. I ett program kan du få den med ((a % n) + n) % n.

Exempel ur vardagen

Veckodagar räknas modulo 7. Är det måndag i dag och du vill veta vilken dag det är om 100 dagar räknar du 100 mod 7 = 2. Det blir två dagar efter måndag, alltså onsdag. Det är samma idé som veckodagskalkylatorn använder. Rullande scheman fungerar likadant: ett skiftschema som upprepas var femte vecka avgör vilket pass som gäller med veckonumret modulo 5, som i skiftschemakalkylatorn.

Inom datorer används modulo hela tiden: för att växla mellan jämna och udda rader (n mod 2), för kontrollsiffror i personnummer och bankkonton, och när tal skrivs i andra baser. Varje siffra i en annan talbas är en rest, vilket talbasomvandlaren visar.

Stora potenser modulo n

Vad är sista siffran i $7^{222}$? Sista siffran är resten modulo 10, och kalkylatorn ger 9. Talet själv har nästan 190 siffror, men man behöver aldrig räkna ut det. Ta resten efter varje multiplikation, så håller sig talen små. Metoden kvadrera och multiplicera skriver exponenten binärt och kvadrerar upprepade gånger, så även enorma exponenter kräver bara några tiotal steg.

Ett annat exempel är $2^{100}$ mod 7. Potenserna av 2 modulo 7 upprepar sig: 2, 4, 1, 2, 4, 1 … Perioden är 3, och 100 = 3 · 33 + 1, så svaret blir samma som för $2^1$, alltså 2. Den här sortens mönster är en vanlig provuppgift.

Invers modulo n

Inversen till a modulo n är talet x som gör att a · x ger resten 1. Inversen till 3 modulo 11 är 4, eftersom 3 · 4 = 12 och 12 mod 11 = 1. Den finns bara om a och n saknar gemensamma faktorer, alltså om största gemensamma delaren är 1. Därför saknar 6 inversen modulo 9, eftersom båda är delbara med 3.

Inversen räknas ut med den utökade Euklides algoritm. Den börjar som vanliga Euklides, med upprepade divisioner med rest, och räknar sedan baklänges för att skriva 1 som en kombination av a och n. Inverser modulo n används bland annat i krypteringsmetoden RSA, där en hemlig nyckel är inversen till en offentlig.

Vanliga fel

• Att få en negativ rest och tro att det är fel svar. Det är en annan konvention, se avsnittet om negativa tal.
• Att blanda ihop mod med procent. Tecknet % betyder rest i programmering men procent i vanlig text.
• Att räkna ut hela potensen först. 7 upphöjt till 222 får inte plats i en räknare, men resten går lätt att få fram stegvis.
• Att tro att alla tal har en invers. Bara tal som saknar gemensam faktor med n har det. Är n ett primtal har alla tal som inte är delbara med n en invers.
• Att dela med 0. a mod 0 är inte definierat.

Modulo och delbarhet

a är delbart med n precis när a mod n = 0. Det gör modulo till ett snabbt test för delbarhet. Alla jämna tal har resten 0 modulo 2. Många delbarhetsregler kan förklaras med modulo: ett tal och dess siffersumma har samma rest modulo 9, eftersom 10 ger resten 1 modulo 9. Om ett tal är ett primtal avgörs också med rester: inget mindre tal än talet självt, utom 1, får ge resten 0.

Så gör du på räknaren

Saknar räknaren en mod-funktion räknar du a − n · heltalsdelen av a/n. För 17 och 5: 17 / 5 = 3,4, heltalsdelen är 3, och 17 − 5 · 3 = 2. Var försiktig med negativa tal, där du ska avrunda kvoten nedåt och inte bara stryka decimalerna. Divisionen steg för steg finns i långdivisionskalkylatorn.

Fler kalkylatorer om heltal finns bland kalkylatorerna för talteori och aritmetik och på matematiksidan.