Den kinesiske restklassesætning forklaret
Et tal giver rest 2 ved division med 3, rest 3 ved division med 5 og rest 2 ved division med 7. Hvilket tal er det? Prøv tallene ét for ét, og efter et stykke tid når du 23, men spørgsmålet gemmer på en sætning: så længe divisorerne ikke har nogen fælles faktor, er der altid præcis ét svar under deres produkt, og det kan findes uden at prøve noget. Sætningen er omkring 1.500 år gammel og arbejder stadig i kalendere, i computeres regning og i den kryptografi, der beskytter nettet.
En opgave fra Sunzi Suanjing
Sunzi Suanjing, en kinesisk regnebog fra 3. til 5. århundrede, spørger efter et antal ting, der giver 2 tilbage, når de tælles tre ad gangen, 3 tilbage fem ad gangen og 2 tilbage syv ad gangen. Svaret er 23, og metoden er den, der stadig undervises i: tag 70 for hver ting, der bliver tilbage ved optælling tre ad gangen, 21 for hver ved optælling fem ad gangen og 15 for hver ved optælling syv ad gangen, læg sammen og træk 105 fra så mange gange, som det kan lade sig gøre. 2 × 70 + 3 × 21 + 2 × 15 = 233, og 233 − 2 × 105 = 23. Et vers fra Ming-tiden holdt tallene 70, 21, 15 og 105 i hukommelsen i århundreder. Qin Jiushao gav en generel metode i 1247, samme opgave står i Fibonaccis Liber Abaci fra 1202, og Carl Friedrich Gauss formulerede sætningen i dens moderne form i sine Disquisitiones Arithmeticae fra 1801.
Hvad sætningen siger
Tag moduli n₁, n₂, …, nₖ, hvor ingen to har en fælles faktor, og vilkårlige rester a₁, a₂, …, aₖ. Så findes der præcis ét heltal x fra 0 til N − 1, hvor N = n₁ × n₂ × … × nₖ, der giver resten aᵢ ved division med nᵢ for hvert i. Alle andre løsninger adskiller sig fra det med et multiplum af N. I den modulære aritmetiks notation: systemet x ≡ aᵢ (mod nᵢ) har en løsning, og den er entydig mod N. Sagt på en anden måde bærer et tal fra 0 til N − 1 og listen over dets rester præcis den samme information: 3 × 5 × 7 = 105 tal og 3 × 5 × 7 = 105 mulige lister af rester, hver brugt én gang.
At bygge løsningen
Tallene 70, 21 og 15 er ikke magi. Hvert af dem giver rest 1 ved division med sit eget modulus og rest 0 ved division med de andre: 70 = 2 × 35 er et multiplum af 5 og 7 og giver rest 1 ved division med 3. Generelt tager man Nᵢ = N / nᵢ, et multiplum af hvert modulus undtagen nᵢ, og ganger det med yᵢ, den inverse af Nᵢ mod nᵢ. Den inverse findes, fordi Nᵢ og nᵢ ikke har nogen fælles faktor, og den udvidede euklidiske algoritme finder den: den udfører Euklids divisioner for den største fælles divisor og regner baglæns til Bézouts identitet 1 = s × nᵢ + t × Nᵢ, så t er den inverse. Så passer x = a₁N₁y₁ + a₂N₂y₂ + …, reduceret mod N, til hver ligning, fordi hvert led passer til sin egen ligning og forsvinder i alle de andre.
Én ligning ad gangen
Der er en anden vej, som ikke kræver produktet af alle moduli. Enhver løsning til x ≡ 2 (mod 3) har formen x = 2 + 3t. Sæt det ind i den næste ligning: 2 + 3t ≡ 3 (mod 5), altså 3t ≡ 1 (mod 5), og ganges med 2, den inverse af 3 mod 5, fås t ≡ 2 (mod 5). Så er x = 2 + 3 × 2 = 8, og de to første ligninger siger tilsammen x ≡ 8 (mod 15). Gentag med den tredje ligning: 8 + 15t ≡ 2 (mod 7) giver t ≡ 1, så x ≡ 23 (mod 105). Denne indsættelse holder tallene mindre, er den måde, en computer normalt løser sådanne systemer på, og virker stadig, når moduli har en fælles faktor.
Moduli med en fælles faktor
Hvis to moduli har en fælles faktor, overlapper deres ligninger: x ≡ 1 (mod 4) siger allerede, at x er ulige, og x ≡ 4 (mod 6) siger, at x er lige, så intet x opfylder begge. Generelt kan x ≡ a (mod m) og x ≡ b (mod n) gælde samtidig netop når a og b giver samme rest ved division med g = gcd(m, n), altså når g går op i a − b. Så er løsningen entydig mod lcm(m, n) = m × n / g, ikke mod m × n. Den gamle gåde om kurven med æg, der giver 1 tilbage, når de tages op 2, 3, 4, 5 eller 6 ad gangen, og ingen 7 ad gangen, har svaret 301, der gentages for hver 420 = lcm(2, 3, 4, 5, 6, 7). Et system har en løsning netop når hvert par af dets ligninger stemmer overens, så et uløseligt system indeholder altid et par, der støder sammen.
Kalendere, computere og RSA
I 1583 kombinerede Joseph Scaliger tre kalendercykler, solcyklussen på 28 år, månecyklussen på 19 år og indiktionen på 15 år, til den julianske periode på 28 × 19 × 15 = 7.980 år. Ifølge sætningen har hvert år sin egen kombination af de tre cyklusnumre, og perioden begynder i 4713 f.Kr., det sidste år, hvor alle tre var 1; astronomer tæller stadig julianske dage derfra. Computere bruger sætningen til at regne med enorme tal som lister af små rester, der kan lægges sammen og ganges hver for sig og parallelt og samles til sidst. RSA-dekryptering virker på samme måde: c^d mod n med n = p × q beregnes som to potenser mod p og mod q, der samles med sætningen, omkring fire gange hurtigere end én potens mod n. Ordninger til deling af hemmeligheder, som Mignottes og Asmuth og Blooms, gemmer en hemmelighed i rester, så kun nok af dem tilsammen afslører den.
Prøv det selv
Åbn lommeregneren for at skrive et vilkårligt kongruenssystem, op til 20 ligninger og tal på op til 200 cifre, eller vælg et af regneeksemplerne: Sunzis opgave, kurven med æg, den julianske periode, to buskøreplaner, RSA-dekryptering og et system uden løsning. Udregningen står med dine tal, via konstruktionen eller via indsættelse, med den udvidede euklidiske algoritme for hver invers. Billedet markerer de tal, der opfylder hver ligning, så du ser den ene kolonne, hvor de alle mødes, eller lægger resterne af to ligninger ud i en tabel, hvor hvert tal har sin egen celle.
Ofte stillede spørgsmål
Er løsningen til et kongruenssystem entydig?
Kun op til et multiplum af modulus. Hvis x = 23 løser Sunzis opgave, gør 23 + 105 = 128, 233 og −82 det også, fordi det at lægge 105 til ikke ændrer nogen af resterne. Sætningen siger, at der er præcis én løsning fra 0 til 104; med moduli med fælles faktorer præcis én under deres mindste fælles multiplum.
Hvorfor skal moduli være indbyrdes primiske?
For konstruktionen, fordi Nᵢ skal have en invers mod nᵢ, og den findes kun, når de ikke har nogen fælles faktor. For selve sætningen, fordi fælles faktorer får nogle ligninger til at overlappe: så har et system enten ingen løsning eller færre forskellige, og løsningerne gentages for hvert mindste fælles multiplum i stedet for hvert produkt.
Hvordan finder jeg en modulær invers i hånden?
Med den udvidede euklidiske algoritme. For den inverse af 15 mod 7: 15 = 2 × 7 + 1, så 1 = 15 − 2 × 7, og 15 × 1 ≡ 1 (mod 7): den inverse er 1. For 35 mod 3: 35 = 11 × 3 + 2 og 3 = 1 × 2 + 1, så 1 = 3 − 2 = 3 − (35 − 11 × 3) = 12 × 3 − 35, og den inverse af 35 mod 3 er −1 ≡ 2. For små moduli kan man også bare prøve 1, 2, 3, …, indtil produktet giver rest 1.
Hvad har sætningen med ure at gøre?
En rest mod n er en stilling på et ur med n timer. To ure med 3 og 5 timer, der starter sammen og rykker én time frem ad gangen, viser hvert af de 15 par af stillinger én gang, før de er tilbage ved start, fordi 3 og 5 ikke har nogen fælles faktor. Ure med 4 og 6 timer er tilbage efter 12 skridt og viser kun 12 af de 24 par: en ulige og en lige stilling optræder aldrig sammen.
Er du klar til at prøve?
Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.
Åbn lommeregneren til den kinesiske restklassesætning