Kinesiska restsatsen förklarad
Ett tal ger resten 2 vid division med 3, resten 3 vid division med 5 och resten 2 vid division med 7. Vilket tal är det? Pröva talen ett i taget så når du 23 efter en stund, men frågan döljer en sats: så länge divisorerna inte har någon gemensam faktor finns det alltid exakt ett svar under deras produkt, och det går att hitta utan att pröva något. Satsen är ungefär 1 500 år gammal och arbetar fortfarande i kalendrar, i datorers räkning och i den kryptografi som skyddar webben.
Ett problem ur Sunzi Suanjing
Sunzi Suanjing, en kinesisk räknebok från 200- till 400-talet, frågar efter ett antal saker som lämnar 2 när de räknas tre åt gången, 3 fem åt gången och 2 sju åt gången. Svaret är 23, och metoden är den som fortfarande lärs ut: ta 70 för varje sak som blir över när man räknar tre åt gången, 21 för varje när man räknar fem åt gången och 15 för varje när man räknar sju åt gången, addera och dra av 105 så många gånger det går. 2 × 70 + 3 × 21 + 2 × 15 = 233, och 233 − 2 × 105 = 23. En vers från Mingdynastin höll talen 70, 21, 15 och 105 i minnet i århundraden. Qin Jiushao gav en allmän metod 1247, samma problem finns i Fibonaccis Liber Abaci från 1202, och Carl Friedrich Gauss formulerade satsen i sin moderna form i Disquisitiones Arithmeticae från 1801.
Vad satsen säger
Ta moduler n₁, n₂, …, nₖ där inga två har en gemensam faktor, och godtyckliga rester a₁, a₂, …, aₖ. Då finns det exakt ett heltal x från 0 till N − 1, där N = n₁ × n₂ × … × nₖ, som ger resten aᵢ vid division med nᵢ för varje i. Alla andra lösningar skiljer sig från det med en multipel av N. I moduloräkningens notation: systemet x ≡ aᵢ (mod nᵢ) har en lösning, och den är entydig mod N. Med andra ord bär ett tal från 0 till N − 1 och listan över dess rester exakt samma information: 3 × 5 × 7 = 105 tal och 3 × 5 × 7 = 105 möjliga restlistor, var och en använd en gång.
Att bygga lösningen
Talen 70, 21 och 15 är ingen magi. Vart och ett ger resten 1 vid division med sin egen modul och resten 0 vid division med de andra: 70 = 2 × 35 är en multipel av 5 och 7 och ger resten 1 vid division med 3. Allmänt tar man Nᵢ = N / nᵢ, en multipel av varje modul utom nᵢ, och multiplicerar den med yᵢ, inversen till Nᵢ mod nᵢ. Inversen finns eftersom Nᵢ och nᵢ inte har någon gemensam faktor, och den utvidgade euklidiska algoritmen hittar den: den utför Euklides divisioner för största gemensamma delaren och räknar baklänges till Bézouts identitet 1 = s × nᵢ + t × Nᵢ, så att t är inversen. Då passar x = a₁N₁y₁ + a₂N₂y₂ + …, reducerat mod N, varje ekvation, eftersom varje term passar sin egen ekvation och försvinner i alla andra.
En ekvation i taget
Det finns ett andra sätt som inte behöver produkten av alla moduler. Varje lösning till x ≡ 2 (mod 3) har formen x = 2 + 3t. Sätt in det i nästa ekvation: 2 + 3t ≡ 3 (mod 5), alltså 3t ≡ 1 (mod 5), och multiplikation med 2, inversen till 3 mod 5, ger t ≡ 2 (mod 5). Då är x = 2 + 3 × 2 = 8, och de två första ekvationerna säger tillsammans x ≡ 8 (mod 15). Upprepa med den tredje ekvationen: 8 + 15t ≡ 2 (mod 7) ger t ≡ 1, så x ≡ 23 (mod 105). Den här insättningen håller talen mindre, är det sätt en dator oftast löser sådana system på och fungerar även när modulerna har en gemensam faktor.
Moduler med en gemensam faktor
Om två moduler har en gemensam faktor överlappar deras ekvationer: x ≡ 1 (mod 4) säger redan att x är udda, och x ≡ 4 (mod 6) säger att x är jämnt, så inget x uppfyller båda. Allmänt kan x ≡ a (mod m) och x ≡ b (mod n) gälla samtidigt precis när a och b ger samma rest vid division med g = gcd(m, n), det vill säga när g delar a − b. Då är lösningen entydig mod lcm(m, n) = m × n / g, inte mod m × n. Den gamla gåtan om äggkorgen, som lämnar 1 när äggen tas upp 2, 3, 4, 5 eller 6 åt gången och inget när de tas upp 7 åt gången, har svaret 301, som upprepas var 420 = lcm(2, 3, 4, 5, 6, 7):e tal. Ett system har en lösning precis när varje par av dess ekvationer stämmer överens, så ett olösligt system innehåller alltid ett par som krockar.
Kalendrar, datorer och RSA
År 1583 kombinerade Joseph Scaliger tre kalendercykler, solcykeln på 28 år, mångcykeln på 19 år och indiktionen på 15 år, till den julianska perioden på 28 × 19 × 15 = 7 980 år. Enligt satsen har varje år sin egen kombination av de tre cykelnumren, och perioden börjar 4713 f.Kr., det senaste året då alla tre var 1; astronomer räknar fortfarande julianska dagar därifrån. Datorer använder satsen för att räkna med enorma tal som listor av små rester, som kan adderas och multipliceras var för sig och parallellt och sättas ihop i slutet. RSA-dekryptering fungerar på samma sätt: c^d mod n med n = p × q beräknas som två potenser mod p och mod q som sätts ihop med satsen, ungefär fyra gånger snabbare än en potens mod n. System för hemlighetsdelning, som Mignottes och Asmuths och Blooms, gömmer en hemlighet i rester så att bara tillräckligt många av dem tillsammans avslöjar den.
Pröva själv
Öppna kalkylatorn för att skriva vilket kongruenssystem som helst, upp till 20 ekvationer och tal på upp till 200 siffror, eller välj ett av räkneexemplen: Sunzis problem, äggkorgen, den julianska perioden, två busstidtabeller, RSA-dekryptering och ett system utan lösning. Uträkningen skrivs ut med dina tal, med konstruktionen eller med insättning, med den utvidgade euklidiska algoritmen för varje invers. Bilden markerar talen som uppfyller varje ekvation, så att du ser den enda kolumnen där alla möts, eller lägger ut resterna av två ekvationer i en tabell där varje tal har sin egen cell.
Ofta ställda frågor
Är lösningen till ett kongruenssystem entydig?
Bara upp till en multipel av modulen. Om x = 23 löser Sunzis problem gör även 23 + 105 = 128, 233 och −82 det, eftersom att lägga till 105 inte ändrar någon av resterna. Satsen säger att det finns exakt en lösning från 0 till 104; med moduler som har gemensamma faktorer exakt en under deras minsta gemensamma multipel.
Varför måste modulerna vara relativt prima?
För konstruktionen, eftersom Nᵢ måste ha en invers mod nᵢ, och den finns bara när de inte har någon gemensam faktor. För själva satsen, eftersom gemensamma faktorer får vissa ekvationer att överlappa: då har ett system antingen ingen lösning eller färre olika, och lösningarna upprepas var minsta gemensamma multipel i stället för var produkt.
Hur hittar jag en modulär invers för hand?
Med den utvidgade euklidiska algoritmen. För inversen till 15 mod 7: 15 = 2 × 7 + 1, alltså 1 = 15 − 2 × 7, och 15 × 1 ≡ 1 (mod 7): inversen är 1. För 35 mod 3: 35 = 11 × 3 + 2 och 3 = 1 × 2 + 1, alltså 1 = 3 − 2 = 3 − (35 − 11 × 3) = 12 × 3 − 35, och inversen till 35 mod 3 är −1 ≡ 2. För små moduler kan man också helt enkelt pröva 1, 2, 3, … tills produkten ger resten 1.
Vad har satsen med klockor att göra?
En rest mod n är ett läge på en klocka med n timmar. Två klockor med 3 och 5 timmar som startar samtidigt och flyttas fram en timme i taget visar vart och ett av de 15 paren av lägen en gång innan de är tillbaka vid start, eftersom 3 och 5 inte har någon gemensam faktor. Klockor med 4 och 6 timmar är tillbaka efter 12 steg och visar bara 12 av de 24 paren: ett udda och ett jämnt läge förekommer aldrig tillsammans.
Redo att prova det?
Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.
Öppna kalkylatorn för kinesiska restsatsen