Förstå modulär aritmetik intuitivt (Klockmatematik och varför resten styr)

Klockan är nio och ett flyg går om fem timmar. Visaren hamnar på två, inte på fjorton, för en urtavla har ingen fjorton. Timmarna slår runt vid tolv och börjar om. Du räknade ut det utan att tänka, och du har räknat modulärt sedan du lärde dig klockan; du har bara aldrig mött beteckningen.

Det är hela ämnet. Välj ett tal att slå runt vid, glöm varje fullbordat varv och behåll bara var du landar. Vad som gör det värt en artikel är att den här enda vanan, att bara behålla resten, löser problem som ser omöjliga ut rakt framifrån: sista siffran i ett tal med sjuttio siffror, om ett enormt tal är delbart med 9, varför ett kontokortsnummer är giltigt eller inte, och hur ett meddelande kan krypteras så att bara den avsedda läsaren kan läsa det.

Den här artikeln är bilden: vad en rest egentligen är, varför du får reducera innan du räknar, vad som händer med negativa tal och med potenser, och var den enda ärliga svårigheten, divisionen, kommer ifrån.

En rest är var du landar, inte vad som blir kvar

Standarddefinitionen säger att $a \bmod n$ är resten när $a$ divideras med $n$. Det stämmer, och det är också skälet till att ämnet känns som en plikt, eftersom "rest" låter som skrotet som blir kvar efter en division, en efterhandstanke.

Bättre bild: en rundbana med $n$ markeringar på, numrerade $0$ till $n-1$. För att hitta $a \bmod n$ startar du vid $0$ och går $a$ steg runt banan. Där du stannar är svaret. Att gå 17 steg runt en bana med 5 markeringar tar dig tre hela varv (15 steg) och sedan 2 steg till, så du stannar vid markering 2. Alltså är $17 \bmod 5 = 2$. De hela varven är kvoten; var du landar är resten.

Den här bilden gör två saker som definitionen inte gör. Den får resten att alltid landa i intervallet $0$ till $n-1$, eftersom det är de enda markeringar som finns. Och den förklarar varför två tal kan vara "samma" modulo $n$ även när de är vilt olika: $2$, $17$, $102$ och $5{,}000{,}002$ stannar alla vid markering 2 på en bana med 5 markeringar. De skiljer sig med varv, och banan minns inga varv.

Matematiker skriver den idén som en kongruens:

$$17 \equiv 2 \pmod{5}$$

Läs det som "17 landar där 2 landar, på 5-banan". Trippelstrecket är inget likhetstecken, eftersom 17 och 2 inte är lika. Det säger att de är utbytbara för varje fråga som bara bryr sig om positionen på banan. Den exakta versionen: $a \equiv b \pmod{n}$ betyder att $n$ delar $a - b$, vilket bara är ett annat sätt att säga att de två talen skiljer sig med ett helt antal varv.

Addition och multiplikation bryr sig bara om var du är

Här är det faktum som gör modulär aritmetik till ett verktyg snarare än en kuriositet. Om du ska addera två tal och sedan ta resten kan du ta resterna först, addera dem och reducera igen. Svaret är identiskt. Detsamma gäller för subtraktion och multiplikation.

På banan är det uppenbart. Att addera 17 betyder att gå 17 steg, vilket är tre varv plus 2. De tre varven tar dig tillbaka dit du startade och ändrar ingenting, så att addera 17 har exakt samma effekt som att addera 2. Varven som ligger gömda inne i ett tal är dödvikt, och de förblir dödvikt genom addition och genom multiplikation, eftersom en multipel av $n$ gånger vad som helst fortfarande är en multipel av $n$.

Utskrivet, med $a = qn + r$ och $b = pn + s$:

$$ab = (qn + r)(pn + s) = n(qpn + qs + rp) + rs$$

Allt i den första parentesen är varv. Bara $rs$ överlever, så $ab \bmod n$ är $rs \bmod n$. Resterna bär all information frågan behöver.

Det är därför tipset i Math Zens aritmetikämne säger att du ska reducera steg för steg i stället för att räkna ut hela värdet. Anta att du vill ha $123 \times 456 \bmod 7$. Du kan multiplicera ihop till 56 088 och göra en lång division med 7. Eller så lägger du märke till att $123 = 119 + 4$, så $123 \equiv 4$, och att $456 = 455 + 1$, så $456 \equiv 1$, och svaret är $4 \times 1 = 4$. Två små reduktioner ersätter en multiplikation med fyrsiffriga tal. Vanan är: låt aldrig ett tal växa förbi $n$ om du bara bryr dig om dess rest.

Negativa tal går åt andra hållet

Banbilden hanterar också det fall som snubblar flest. Vad är $-3 \bmod 5$?

Gå 3 steg bakåt från 0 på en bana med 5 markeringar. Du passerar 4, sedan 3, och landar på 2. Alltså är $-3 \equiv 2 \pmod{5}$. Ett negativt tal är bara en vandring i motsatt riktning, samma idé som i Förstå negativa tal intuitivt, och resten är fortfarande var du landar, fortfarande mellan $0$ och $n-1$.

Genvägen: lägg till varv tills talet är positivt. $-3 + 5 = 2$. För $-14 \bmod 5$ lägger du till 15 (tre varv) och får 1. Kalkylatorer och programmeringsspråk är oense om negativa rester, och vissa returnerar $-4$ för $-14 \bmod 5$, så på ett prov ska du alltid ange svaret som den icke-negativa markeringen på banan, och kontrollera vad din kalkylator gör innan du litar på den.

Subtraktion är samma historia. $3 - 8 \pmod{5}$ är $-5$, vilket är exakt ett varv bakåt, så svaret är 0. Eller reducera först: $8 \equiv 3$, så $3 - 3 = 0$.

Sista siffran i en enorm potens

Det här är problemet som övertygar folk om att ämnet är värt att kunna, och det är en direkt följd av regeln om att reducera först.

Sista siffran i ett tal är talet modulo 10, eftersom tiotalen, hundratalen och allt ovanför är multiplar av 10 och landar tillbaka på 0 på en bana med 10 markeringar. Så "vad är sista siffran i $7^{100}$" är samma fråga som "vad är $7^{100} \bmod 10$", och du behöver aldrig beräkna $7^{100}$.

I stället följer du potenserna av 7 runt 10-banan och reducerar varje gång:

• $7^1 = 7$
• $7^2 = 49 \equiv 9$
• $7^3 \equiv 9 \times 7 = 63 \equiv 3$
• $7^4 \equiv 3 \times 7 = 21 \equiv 1$
• $7^5 \equiv 1 \times 7 = 7$

När du väl träffar 1 startar cykeln om: 7, 9, 3, 1, 7, 9, 3, 1, med perioden 4. Eftersom $100 = 4 \times 25$ sitter den hundrade potensen i slutet av en fullständig cykel, på samma plats som $7^4$, och dess sista siffra är 1.

Varje bas har en cykel modulo 10, och de flesta är korta. Potenser av 2 cyklar genom 2, 4, 8, 6. Potenser av 3 genom 3, 9, 7, 1. Potenser av 5 och 6 rör sig aldrig. Metoden är alltid densamma: hitta cykelns längd genom att reducera medan du går, dividera exponenten med cykellängden, och resten av den divisionen talar om var i cykeln du befinner dig. Det är exponenternas idé om upprepad multiplikation, körd på en rundbana i stället för på en rak linje.

Varför siffersummetestet för 9 fungerar

Alla lär sig att ett tal är delbart med 9 om dess siffror summerar till en multipel av 9, och nästan ingen lär sig varför. Modulär aritmetik gör det till ett argument på en rad.

Tio är ett varv plus ett på 9-banan: $10 \equiv 1 \pmod{9}$. Då är $100 = 10 \times 10 \equiv 1 \times 1 = 1$, och varje tiopotens är kongruent med 1 också. Så ett tal som $4{,}527 = 4 \times 1000 + 5 \times 100 + 2 \times 10 + 7$ är kongruent med $4 + 5 + 2 + 7 = 18 \pmod{9}$, och 18 är $0$ på 9-banan, så 4 527 är delbart med 9. Siffersumman är inget trick. Den är talet självt, sett modulo 9.

Testet för 3 fungerar av samma skäl, eftersom $10 \equiv 1 \pmod{3}$ också. Testet för 11 kommer från $10 \equiv -1 \pmod{11}$, vilket gör att tiopotenserna växlar mellan $1$ och $-1$ och ger den alternerande siffersumman. Alla delbarhetsregler du blev tillsagd att memorera är ett enda faktum, "reducera tiopotenserna", tillämpat på olika banor.

Kontrollsiffror: modulär aritmetik i din plånbok

Varje ISBN, varje kontokortsnummer och varje streckkod slutar med en siffra vars enda uppgift är att vara en rest.

Sista siffran i ett trettonsiffrigt ISBN väljs så att en viktad summa av alla tretton siffrorna, med vikterna växelvis 1 och 3, är kongruent med $0 \pmod{10}$. Slinter du på en enda siffra landar summan någon annanstans på 10-banan, och skannern avvisar den. Kontokort använder Luhns algoritm, en något smartare viktning som också fångar de flesta fall där två intilliggande siffror kastas om, igen genom att kontrollera en summa modulo 10.

Det här är de anspråkslösa kusinerna till en mycket större tillämpning. Modern kryptering vilar på att det är lätt att upphöja ett tal till en potens modulo ett mycket stort $n$, medan det inte är lätt att vända processen utan en hemlig nyckel. Cykeljakten du gjorde ovan för $7^{100}$ är samma operation, uppskalad till tal med hundratals siffror, och regeln om att reducera medan du går är det enda skälet till att den går att beräkna alls.

Division är där banan blir ojämn

Addition, subtraktion och multiplikation beter sig på en bana precis som de gör på tallinjen. Division gör det inte, och det är på det enda stället som ämnet förtjänar sitt rykte.

På den vanliga tallinjen betyder att dividera med 4 att multiplicera med $\tfrac{1}{4}$, talet som gånger 4 ger 1. Finns det på 12-banan någon markering som gånger 4 landar på 1? Prova alla: $4 \times 1 = 4$, $4 \times 2 = 8$, $4 \times 3 = 12 \equiv 0$, $4 \times 4 = 16 \equiv 4$, och mönstret 4, 8, 0 upprepas i all evighet. Det träffar aldrig 1. Så på 12-banan finns det inget som heter att dividera med 4.

Skälet är att 4 och 12 delar en faktor. Börja med en multipel av 4, lägg till eller ta bort varv om 12, och du har fortfarande en multipel av 4, så du kan aldrig landa 1 steg efter en multipel av 12. Prova 5 i stället: $5 \times 5 = 25 = 24 + 1 \equiv 1$, så 5 är sin egen invers på 12-banan och att dividera med 5 går bra. Regeln: $a$ har en invers modulo $n$ precis när $a$ och $n$ inte delar någon gemensam faktor utöver 1.

Den regeln har en slående följd. Om $n$ är ett primtal delar ingenting från $1$ till $n - 1$ en faktor med det, så varje nollskild markering har en invers och du kan dividera fritt. Primtalsbanor är de banor där alla fyra räknesätten fungerar, vilket är en stor del av varför primtalen, vars tillgång primtalens oändlighet garanterar, sitter i centrum av talteorin och av kryptografin.

Var misstagen uppstår

Modulär aritmetik har få rörliga delar, och felen är på motsvarande sätt specifika.

Det första är att reducera exponenten i stället för basen. I $7^{100} \bmod 10$ får du reducera 7 modulo 10 (det är redan gjort), och du får reducera exponenten modulo cykellängden när du väl känner den, men du får inte reducera 100 modulo 10 och räkna ut $7^0$. Exponenter bor på en annan bana, den vars storlek är cykellängden, och att blanda ihop de två banorna är det absolut vanligaste felet i det här ämnet.

Det andra är en negativ rest. $-14 \bmod 5$ är 1, inte $-4$. Samma position på banan, men bara det ena är det konventionella namnet, och rättningsmallar vill ha det icke-negativa.

Det tredje är att dividera utan att kontrollera att det finns en invers. Att förkorta bort en gemensam faktor från båda sidor av en kongruens är tillåtet bara om den faktorn inte delar något med modulen. Från $4 \times 2 \equiv 4 \times 5 \pmod{12}$, som är sant eftersom båda sidor är 8, kan du inte förkorta bort 4 och dra slutsatsen att $2 \equiv 5$, vilket är falskt. Varven du slänger bort när du förkortar måste vara varv på den ursprungliga banan.

Det fjärde är att glömma att reducera till slut. Att få $rs = 21$ på en 7-bana och skriva 21 är inte precis fel, men det är inget svar heller. Svaret är en markering på banan, och 21 är tre varv, så markeringen är 0.

Där Math Zen kommer in i bilden

Math Zens aritmetikämne har en egen avdelning för modulär aritmetik, och progressionen är byggd runt vanan att reducera först snarare än runt beteckningarna. Tidiga uppgifter frågar efter enkla rester och kongruenser med små moduler, till dess att "var landar jag" sitter automatiskt. Mellanavdelningarna blandar in negativa tal och produkter, där poängen är att reducera varje faktor innan du multiplicerar och att ange den icke-negativa resten. De senare avdelningarna är uppgifterna om sista siffran och cykellängden, de som dyker upp på tävlingsprov och antagningsprov och som straffar var och en som försöker räkna ut hela potensen.

Eftersom passen är korta och uppgifterna kommer tillbaka med mellanrum, som beskrivs i spridd repetition för matematikträning, blir cykeljakten en reflex i stället för en procedur du slår upp. De flesta har inte en lucka i modulär aritmetik som ett kapitel skulle fylla. De har en bild, banan, som aldrig ritades upp för dem, och ungefär fyrtio repetitioner som aldrig blev gjorda.

Sammanfattning

Modulär aritmetik är aritmetik på en rundbana med $n$ markeringar. En rest är var du landar efter att ha gått $a$ steg, hela varv glöms bort, och två tal är kongruenta när de landar på samma markering. Eftersom varv inte bidrar med något till summor och produkter får du reducera varje tal till dess rest innan du adderar eller multiplicerar, och den enda tillåtelsen förvandlar omöjliga beräkningar, som sista siffran i $7^{100}$, till korta cykler du kan följa för hand. Delbarhetstesten är tiopotenserna reducerade modulo 9, 3 eller 11. Kontrollsiffror är rester som fångar felskrivningar. Division fungerar bara när talet inte delar någon faktor med banan, vilket är varför primtalsbanor är speciella.

När ett moduloproblem kör fast: rita banan. Fråga var varje del landar, reducera medan du går, och håll exponenten på sin egen bana. Svaret är en markering mellan $0$ och $n - 1$, och bilden tar dig dit före formeln gör det.