Hoppa till innehållet

Hur fungerar modulo, även med negativa tal?

Rester enligt alla teckenregler, modulära potenser och inverser, på en levande urtavla.

Räkneoperation

−31 mod 12

5

−31 = −3 × 12 + 5: resten är det som blir kvar när hela multipler av 12 har tagits bort.

Viktiga värden som tabell
Teckenregelqr
Aldrig negativ (matematik)−35
Tecknet på n (Python, Excel)−35
Tecknet på a (JavaScript, C, Java)−2−7
Kvot q
−3
Kongruens
−31 ≡ 5 (mod 12)
Aldrig negativ (matematik)
5
Tecknet på n (Python, Excel)
5
Tecknet på a (JavaScript, C, Java)
−7

Rester enligt alla teckenregler, modulära potenser och inverser, på en levande urtavla.

Så använder du verktyget

  1. Välj a mod n, en modulär potens aᵇ mod n eller en modulär invers a⁻¹ mod n.
  2. Ange heltalen, eller dra punkten runt urtavlan för att ändra a.
  3. För ett negativt tal väljer du den teckenregel du behöver; svaren från matematiken, Python och JavaScript visas sida vid sida.

Så fungerar det

a mod n är resten r när hela multipler av n har tagits bort: a = q × n + r. Tänk dig en urtavla med n tal och 0 överst: börja på 0 och ta a steg (bakåt för ett negativt a); r är där du landar. 31 timmar före midnatt visar en 12-timmarsklocka 5, eftersom −31 = −3 × 12 + 5.

För negativa tal skiljer sig reglerna i vilket namn de ger den platsen. Matematiken använder den euklidiska resten, som aldrig är negativ (0 ≤ r < |n|). Python och Excel avrundar q nedåt, så r får tecknet på n. JavaScripts %, C och Java avrundar q mot 0, så r får tecknet på a: −31 % 12 är −7 där. Svaren skiljer sig med n och är kongruenta: −7 ≡ 5 (mod 12).

Modulära potenser hittas genom upprepad kvadrering: 4¹³ mod 497 = 445, utan att 4¹³ någonsin skrivs ut i sin helhet. Inversen till a är det x för vilket a × x ≡ 1 (mod n), som hittas med den utökade euklidiska algoritmen: 3 × 4 = 12 ≡ 1 (mod 11), så 3⁻¹ mod 11 = 4. Den finns bara om a och n saknar gemensam faktor. Källor: Khan Academy, modulär aritmetik; OpenStax Contemporary Mathematics, avsnitt 3.7.

Räkneexempel

Vad är −31 mod 12?

  1. Skriv −31 = q × 12 + r. I matematiken är q = −3, alltså r = −31 − (−3 × 12) = 5.
  2. JavaScript och C avrundar kvoten mot 0 i stället: q = −2, så resten blir −7.

5 i matematiken och Python, −7 i JavaScript; de skiljer sig med 12.

Vanliga frågor

Varför ger −7 % 3 −1 i JavaScript men 2 i Python?

JavaScript avrundar kvoten mot 0 (−2), så resten blir −7 − (−6) = −1. Python avrundar nedåt (−3), så det blir −7 − (−9) = 2. Båda är rätt enligt sin egen regel.

Hur får jag alltid en icke-negativ rest i kod?

Använd ((a % n) + n) % n för ett positivt n. Det gör JavaScripts eller C:s trunkerade rest till den euklidiska.

Var används modulär aritmetik?

I klockor och kalendrar, kontrollsiffror som IBAN och ISBN, hashtabeller och kryptering med publika nycklar som RSA, som bygger på modulära potenser och inverser.

Varför finns ingen invers till 4 mod 6?

4 och 6 har den gemensamma faktorn 2, så varje multipel av 4 är jämn modulo 6 och kan aldrig bli 1.

Vad är skillnaden mellan mod och rest?

För positiva tal finns ingen. För negativa tal ger ”mod” oftast ett resultat mellan 0 och n − 1 (eller med n:s tecken), medan en ”rest” som JavaScripts % får samma tecken som a.

Skicka feedback