Kinesiska Restklasssatsen Miniräknare: Lös Modulära System Steg för Steg
En kinesisk restklasssatsen miniräknare löser ett system av samtidiga kongruenser — påståenden som x ≡ 2 (mod 3) och x ≡ 3 (mod 5) — genom att kombinera dem till en enda kongruens modulo produkten (eller minsta gemensam multipel) av de enskilda modulerna. Metoden går tillbaka ungefär 1500 år till den kinesiska matematiska texten Sunzi Suanjing, och idag ligger den till grund för optimeringar av RSA-kryptering, kalenderberäkningar och felkorrigerande koder, förutom att vara en hörnsten i kurserna diskret matematik och talteori. Denna guide går igenom hur miniräknaren fungerar internt, hur man kontrollerar om ett system ens har en lösning, hur man hittar de modulära inverser som metoden är beroende av, två fullt utarbetade exempel — en med parvis relativt prima moduli och en utan — plus vanliga misstag och övningsuppgifter.
Innehåll
- 01Vad är Kinesiska Restklasssatsen?
- 02Hur Fungerar en Kinesiska Restklasssatsen Miniräknare?
- 03Hur Kontrollerar Du om Moduler är Kompatibla?
- 04Vad är en Modulär Invers och Hur Hittar Man En?
- 05Utarbetet Exempel: Lösa Parvis Relativt Prima Kongruenser
- 06Utarbetet Exempel: Försoning av Icke-Relativt Prima Moduli
- 07Rekonstruera den Minsta Icke-Negativa Lösningen
- 08Vilka är de Vanligaste Kinesiska Restklasssatsen Misstagen?
- 09Övningsuppgifter: Testa dina Kinesiska Restklasssatsen Miniräknarfärdigheter
Vad är Kinesiska Restklasssatsen?
Kinesiska Restklasssatsen (KRS) säger att om du har ett system av kongruenser x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), ..., x ≡ aₙ (mod mₙ), och modulerna m₁, m₂, ..., mₙ är parvis relativt prima (varje par har ingen gemensam faktor utom 1), så finns det exakt en lösning för x modulo M, där M = m₁ × m₂ × ... × mₙ. Satsen får sitt namn från sitt tidigaste kända framträdande i den kinesiska texten från 300-400-talet Sunzi Suanjing (Mästare Suns aritmetikmanual), som presenterade det nu klassiska problemet: hitta ett tal som lämnar rest 2 när det delas med 3, rest 3 när det delas med 5 och rest 2 när det delas med 7. Det problemet — och KRS-metoden som löser det — dyker upp ständigt utanför klassrummet: RSA-kryptering använder KRS för att påskynda dekryptering genom att arbeta med mindre moduli istället för en gigantisk, datavetenskap använder den för att representera stora tal som tupler av mindre rester för snabbare aritmetik, och kalendersystem använder den för att försonas cykler av olika längder (veckodagar, dagar i månaden och språngårscykler).
Kinesiska Restklasssatsen: för parvis relativt prima moduli m₁, ..., mₙ, systemet x ≡ aᵢ (mod mᵢ) har exakt en lösning modulo M = m₁ × m₂ × ... × mₙ.
Hur Fungerar en Kinesiska Restklasssatsen Miniräknare?
En kinesisk restklasssatsen miniräknare automatiserar fyra steg som är tråkiga att följa för hand när ett system har tre eller fler kongruenser, särskilt de modulära inversa beräkningarna. Internt behandlar den varje kongruens som ett par (aᵢ, mᵢ), bekräftar att modulerna går att använda tillsammans och byggerar sedan den unika lösningen med en viktad summa snarare än försök och misstag. Att förstå dessa fyra steg är det som gör att du kan verifiera miniräknarens utmatning eller lösa samma problem för hand på ett prov där ingen miniräknare är tillåten.
1. Steg 1: Kontrollera modulerna
Bekräfta att varje par av moduli är relativt prima (sgd = 1). Om något par delar en gemensam faktor, byter miniräknaren till kompatibilitetskontollen som beskrivs i nästa avsnitt istället för standardformeln.
2. Steg 2: Beräkna den kombinerade modulen M
Multiplicera alla moduli tillsammans: M = m₁ × m₂ × ... × mₙ. Detta är modulen för den slutliga kombinerade svaret.
3. Steg 3: Hitta varje delprodunkt och dess modulära invers
För varje kongruens i, beräkna Mᵢ = M / mᵢ (produkten av varje modul utom mᵢ), hitta sedan den modulära inversen av Mᵢ modulo mᵢ — kalla den yᵢ, där Mᵢ × yᵢ ≡ 1 (mod mᵢ).
4. Steg 4: Kombinera och reducera
Summera aᵢ × Mᵢ × yᵢ över varje kongruens, sedan reducera den summan modulo M för att få den unika minsta icke-negativa lösningen x.
Formeln bakom varje kinesisk restklasssatsen miniräknare: x ≡ Σ (aᵢ × Mᵢ × yᵢ) mod M, där Mᵢ = M/mᵢ och yᵢ är den modulära inversen av Mᵢ mod mᵢ.
Hur Kontrollerar Du om Moduler är Kompatibla?
Lärobokversionen av Kinesiska Restklasssatsen kräver parvis relativt prima moduli, men verkliga system — särskilt de som visas upp i schemaläggnings- eller krypteringsproblem — har ofta moduli som delar faktorer. En generaliserad version av KRS gäller fortfarande, men bara om systemet först passar en kompatibilitetskontroll: för varje par av kongruenser x ≡ aᵢ (mod mᵢ) och x ≡ aⱼ (mod mⱼ), måste de två överenskomma på överlappningen, vilket innebär aᵢ ≡ aⱼ (mod sgd(mᵢ, mⱼ)). Om den kontrollen misslyckas för även ett enda par, har systemet ingen lösning alls, oavsett vad annat — och en bra miniräknare rapporterar detta istället för att returnera ett felaktigt tal.
1. Steg 1: Beräkna sgd(mᵢ, mⱼ) för varje par av moduli
För ett två-kongruenssystem finns det bara ett par att kontrollera. För ett tre-kongruenssystem, kontrollera alla tre paren.
2. Steg 2: Reducera båda resterna modulo den sgd
Ta aᵢ mod sgd(mᵢ, mⱼ) och aⱼ mod sgd(mᵢ, mⱼ). Om de matchar är paret kompatibelt.
3. Steg 3: Exempel på ett inkompatibelt system
Ta x ≡ 1 (mod 4) och x ≡ 0 (mod 6). sgd(4, 6) = 2. Reducera: 1 mod 2 = 1, och 0 mod 2 = 0. Eftersom 1 ≠ 0, finns det inget heltal som uppfyller båda kongruenserna — systemet har ingen lösning, och en kinesisk restklasssatsen miniräknare bör flagga exakt detta istället för att tvinga ett svar.
Kompatibilitetsregel för icke-relativt prima moduli: x ≡ aᵢ (mod mᵢ) och x ≡ aⱼ (mod mⱼ) kan båda vara sanna bara om aᵢ ≡ aⱼ (mod sgd(mᵢ, mⱼ)).
Vad är en Modulär Invers och Hur Hittar Man En?
Den modulära inversen av ett tal a modulo m är ett annat tal b sådant att a × b ≡ 1 (mod m) — det spelar samma roll som 1/a spelar i vanlig division, men begränsat till heltal inom ett fast modulo. En modulär invers existerar om och bara om sgd(a, m) = 1, vilket är exakt varför Standard Kinesiska Restklasssatsen kräver parvis relativt prima moduli: det garanterar att varje Mᵢ har en invers mod mᵢ. Det mest tillförlitliga sättet att hitta en modulär invers för hand är den utökade euklidiska algoritmen, som kör den vanliga sgd-algoritmen framåt och sedan arbetar bakåt för att uttrycka 1 som en kombination av a och m.
1. Steg 1: Kör den euklidiska algoritmen framåt
Hitta inversen av 4 mod 7. Dividera upprepade gånger: 7 = 1×4 + 3, sedan 4 = 1×3 + 1, sedan 3 = 3×1 + 0. Resterna är 3, sedan 1, sedan 0, vilket bekräftar sgd(4, 7) = 1, så en invers existerar.
2. Steg 2: Arbeta bakåt för att isolera 1
Från näst sista raden, 1 = 4 − 1×3. Ersätt 3 = 7 − 1×4 från första raden: 1 = 4 − 1×(7 − 1×4) = 2×4 − 1×7.
3. Steg 3: Läs av inversen
Ekvationen 1 = 2×4 − 1×7 betyder 2×4 ≡ 1 (mod 7), så inversen av 4 mod 7 är 2. Snabbkontroll: 4 × 2 = 8 = 7 + 1, vilket verkligen är ≡ 1 (mod 7).
För små moduli är det ofta snabbare att testa kandidater direkt: multiplicera a med 1, 2, 3, ... mod m tills produkten är 1. För större moduli är den utökade euklidiska algoritmen mycket mer tillförlitlig.
Utarbetet Exempel: Lösa Parvis Relativt Prima Kongruenser
Detta är det klassiska Sunzi Suanjing-problemet: hitta x sådant att x ≡ 2 (mod 3), x ≡ 3 (mod 5) och x ≡ 2 (mod 7). Modulerna 3, 5 och 7 är parvis relativt prima, så standard KRS-formeln gäller direkt.
1. Steg 1: Beräkna M
M = 3 × 5 × 7 = 105.
2. Steg 2: Beräkna varje Mᵢ och dess invers
M₁ = 105/3 = 35. 35 mod 3 = 2, och inversen av 2 mod 3 är 2 (eftersom 2×2 = 4 ≡ 1 mod 3). M₂ = 105/5 = 21. 21 mod 5 = 1, och inversen av 1 mod 5 är 1. M₃ = 105/7 = 15. 15 mod 7 = 1, och inversen av 1 mod 7 är 1.
3. Steg 3: Kombinera
x ≡ (a₁×M₁×y₁) + (a₂×M₂×y₂) + (a₃×M₃×y₃) mod M = (2×35×2) + (3×21×1) + (2×15×1) mod 105 = 140 + 63 + 30 mod 105 = 233 mod 105 = 23.
4. Steg 4: Verifiera
23 ÷ 3 = 7 rest 2 ✓. 23 ÷ 5 = 4 rest 3 ✓. 23 ÷ 7 = 3 rest 2 ✓. Den minsta icke-negativa lösningen är x = 23, och varje annan lösning är 23 + 105k för vilket heltal k som helst.
x ≡ 23 (mod 105) — samma svar som en kinesisk restklasssatsen miniräknare returnerar omedelbar, och samma problem som öppnade denna gren av talteori för över tusen år sedan.
Utarbetet Exempel: Försoning av Icke-Relativt Prima Moduli
Nu lösa x ≡ 3 (mod 4) och x ≡ 1 (mod 6), där 4 och 6 inte är relativt prima (de delar en faktor på 2). Standardformeln från det parvis relativt prima exemplet gäller inte direkt, men systemet kan fortfarande ha en unik lösning modulo den minsta gemensamma multipeln av modulerna, förutsatt att det först klarar kompatibilitetskontrollen.
1. Steg 1: Kontrollera kompatibilitet
sgd(4, 6) = 2. Reducera båda resterna: 3 mod 2 = 1, och 1 mod 2 = 1. De matchar, så systemet är kompatibelt och en lösning existerar.
2. Steg 2: Hitta den kombinerade modulen
Istället för att multiplicera 4 × 6 = 24, använd den minsta gemensamma multipeln: mgm(4, 6) = 12. Lösningen blir unik modulo 12, inte 24.
3. Steg 3: Ersätt och lös
Skriv x = 4k + 3 från första kongruensen, ersätt sedan i den andra: 4k + 3 ≡ 1 (mod 6), så 4k ≡ −2 ≡ 4 (mod 6). Båda sidor och modulen delar en faktor på sgd(4, 6) = 2, så dividera hela kongruensen med 2: 2k ≡ 2 (mod 3). Inversen av 2 mod 3 är 2, så k ≡ 2×2 ≡ 1 (mod 3).
4. Steg 4: Rekonstruera x
k = 3j + 1 för vilket heltal j som helst, så x = 4(3j + 1) + 3 = 12j + 7. Den minsta icke-negativa lösningen är x = 7.
5. Steg 5: Verifiera
7 mod 4 = 3 ✓. 7 mod 6 = 1 ✓. Så x ≡ 7 (mod 12) är korrekt, och att dividera kongruensen med den delade faktorn — istället för att ignorera den — är steget som gör att icke-relativt prima KRS fungerar.
När moduli delar en gemensam faktor kan du inte använda den parvis relativt prima formeln som den är — du måste dividera den resulterande kongruensen med sgd(mᵢ, mⱼ) innan du hittar inversen, eller inversen kommer inte att existera.
Rekonstruera den Minsta Icke-Negativa Lösningen
Varje kinesisk restklasssatsen system som klarar sin kompatibilitetskontroll har oändligt många heltalslösningar, inte bara en — men de är alla kongruenta med varandra modulo M (eller modulo mgm(m₁, ..., mₙ) i det icke-relativt prima fallet). Enligt konvention rapporterar en miniräknare den minsta icke-negativa representanten för den oändliga familjen, värdet x₀ som uppfyller 0 ≤ x₀ < M, eftersom det är det enda kanoniska svaret som är enklast att ange, jämföra och verifiera. Varje annan lösning är bara x₀ plus eller minus en multipel av M.
1. Reducera en negativ mellanresultat summa
Den vägda summan i Steg 4 av miniräknarmetoden kan komma ut negativ om någon rest aᵢ är negativ eller om en modulär invers beräknades som en negativ representant. Om summan är, säg, S = −37 och M = 45, lägg till M upprepade gånger tills resultatet är icke-negativt: −37 + 45 = 8, så den minsta icke-negativa lösningen är x₀ = 8, inte −37.
2. Den fullständiga lösningsuppsättningen
När du väl har x₀ är den kompletta lösningsuppsättningen varje heltal av formen x₀ + kM för k = ..., −2, −1, 0, 1, 2, .... I Sunzi-exemplet ovan är det 23, 128, 233, ... och även −82, −187, och så vidare — men 23 är den du rapporterar såvida ett specifikt intervall inte begärs.
Ett negativt eller för stort mellanresultat är inte fel — det har bara inte reducerats ännu. Lägg till eller subtrahera multipler av M tills värdet hamnar i [0, M).
Vilka är de Vanligaste Kinesiska Restklasssatsen Misstagen?
De flesta fel i KRS-problem kommer från att hoppa över en kontroll snarare än från en felaktig slutlig beräkning, vilket är varför det lönar sig att sakta ner i början av ett problem snarare än slutet.
1. Tillämpa den relativt prima formeln på icke-relativt prima moduli
Om någon två moduli delar en faktor, beräkning av M som deras raka produkt och sökning av modulära inverser på standardsättet misslyckas tyst eller producerar ett fel svar — kontrollera alltid sgd(mᵢ, mⱼ) = 1 för varje par först.
2. Förvirra en modulär invers med en vanlig reciprok
Inversen av 4 mod 7 är 2, inte 1/4 — modulära inverser är heltal som hittas via den utökade euklidiska algoritmen (eller provmultiplikation för små moduli), aldrig bråk.
3. Inte reducera negativa tal korrekt modulo m
−2 mod 6 är 4, inte −2 och inte 2 — fortsätt att lägga till modulen tills resultatet är i intervallet [0, m). Att trunkera eller ta det absoluta värdet istället för att lägga till modulen är en frekvent källa till fel svar.
4. Glömma att dividera med den delade faktorn i icke-relativt prima system
När moduli delar en gemensam faktor måste en kongruens som 4k ≡ 4 (mod 6) divideras genom med sgd(4, 6) = 2 för att bli 2k ≡ 2 (mod 3) innan du kan hitta en invers — 4 har ingen invers mod 6 alls, eftersom sgd(4, 6) ≠ 1.
5. Sluta innan du reducerar den slutliga summan modulo M
Den vägda summan från Steg 4 (till exempel 233 i Sunzi-problemet) är inte det slutliga svaret — det måste reduceras modulo M (233 mod 105 = 23) för att nå den minsta icke-negativa lösningen.
Om ditt svar inte uppfyller varje ursprunglig kongruens när du pluggar in det igen, kontrollera kompatibilitetskontrollen och de modulära inverserna först — det är där nästan varje KRS-misstag faktiskt händer.
Övningsuppgifter: Testa dina Kinesiska Restklasssatsen Miniräknarfärdigheter
Arbeta igenom dessa tre system för hand, kontrollera först parvis relativt primtalitet eller kompatibilitet, innan du jämför med lösningarna nedan. Det andra problemet är avsiktligt olösbart — att känna igen det är lika viktigt som att hitta ett numeriskt svar när det finns.
1. Problem 1 (parvis relativt prima)
Lös: x ≡ 1 (mod 3), x ≡ 4 (mod 5), x ≡ 6 (mod 7). Svar: M = 105. M₁ = 35 med invers 2 mod 3; M₂ = 21 med invers 1 mod 5; M₃ = 15 med invers 1 mod 7. Summa = (1×35×2) + (4×21×1) + (6×15×1) = 70 + 84 + 90 = 244. 244 mod 105 = 34. Kontrollera: 34 mod 3 = 1 ✓, 34 mod 5 = 4 ✓, 34 mod 7 = 6 ✓. Lösning: x ≡ 34 (mod 105).
2. Problem 2 (inkompatibla moduli — ingen lösning)
Lös: x ≡ 2 (mod 8), x ≡ 5 (mod 12). sgd(8, 12) = 4. Reducera: 2 mod 4 = 2, och 5 mod 4 = 1. Eftersom 2 ≠ 1, är systemet inkompatibelt och har ingen lösning — en kinesisk restklasssatsen miniräknare bör returnera denna slutsats istället för ett felaktigt tal.
3. Problem 3 (kompatibla icke-relativt prima moduli)
Lös: x ≡ 5 (mod 9), x ≡ 2 (mod 6). sgd(9, 6) = 3. Reducera: 5 mod 3 = 2, och 2 mod 3 = 2 — kompatibel. mgm(9, 6) = 18. Skriv x = 9k + 5, ersätt: 9k + 5 ≡ 2 (mod 6) → 9k ≡ −3 ≡ 3 (mod 6). Dividera med sgd(9, 6) = 3: 3k ≡ 1 (mod 2) → k ≡ 1 (mod 2). Så k = 2j + 1, vilket ger x = 9(2j+1) + 5 = 18j + 14. Kontrollera: 14 mod 9 = 5 ✓, 14 mod 6 = 2 ✓. Lösning: x ≡ 14 (mod 18). Om du vill göra en dubbelkontroll av varje modulär invers och reduceringssteg på ett problem som detta, kommer Solvifys steg-för-steg matematiklösare att guida dig genom varje stadium på samma sätt som denna guide gör.
Det snabbaste sättet att bygga verklig behärskning av Kinesiska Restklasssatsen är att lösa en blandning av parvis relativt prima, icke-relativt prima men kompatibla och inkompatibla system — att känna igen vilket fall du är i är halva färdigheten.
Relaterade artiklar
Restklasssatsen Miniräknare: Hur man Hittar Rester Steg för Steg
Ett annat men relaterat restbegrepp — denna guide täcker polynomrestklasssatsen, användbar kontext innan du tacklar modulära kongruenser.
Gaussisk Eliminering Miniräknare: Lös Linjära System Steg för Steg
En annan systematisk, algoritmdriven miniräknare metod — jämför hur gaussisk eliminering och Kinesiska Restklasssatsen varje reducerar ett system till ett enda svar.
Lös Matematikproblem Steg för Steg: Ett Repeterbara Framework för Vilket Problem som Helst
De 5-stegs ramverket i denna guide gäller direkt för KRS-problem: identifiera vad som är givet, välj en metod, arbeta systematiskt och verifiera resultatet.
Relaterade matematiklösare
Smart Skannerlösare
Ta en bild av ett kongruenssystem eller talteori-problem och få en omedelbar steg-för-steg Kinesisk Restklasssatsen lösning.
Steg-för-Steg Lösningar
Se varje modulär invers, kompatibilitetskontroll och reduceringssteg förklarad, inte bara den slutliga resten.
AI Matematiklärare
Ställ uppföljningsfrågor om modulära inverser, relativt prima moduli eller varför ett system inte har någon lösning, med svar anpassade till ditt exakta problem.