Metod för successiv substitution
I modulär aritmetik är metoden för successiv substitution en metod för att lösa problem med samtidiga kongruenser genom att använda definitionen av kongruensekvationen. Det används vanligtvis i fall där villkoren för den kinesiska restsatsen inte är uppfyllda.
Det finns också en icke-relaterad numerisk analysmetod för successiv substitution, en randomiserad algoritm som används för att hitta rot , en tillämpning av fixpunkts iteration .
Metoden för successiv substitution är också känd som backsubstitution.
Exempel
Exempel ett
Betrakta den enkla uppsättningen av samtidiga kongruenser
- x ≡ 3 (mod 4)
- x ≡ 5 (mod 6)
Nu, för att x ≡ 3 (mod 4) ska vara sann, x = 3 + 4 j för något heltal j . Ersätt detta i den andra ekvationen
- 3+4 j ≡ 5 (mod 6)
eftersom vi letar efter en lösning på båda ekvationerna.
Subtrahera 3 från båda sidor (detta är tillåtet i modulär aritmetik)
- 4 j ≡ 2 (mod 6)
Vi förenklar genom att dividera med den största gemensamma delaren av 4,2 och 6. Division med 2 ger:
- 2 j ≡ 1 (mod 3)
Den euklidiska modulära multiplikativa inversen av 2 mod 3 är 2. Efter att ha multiplicerat båda sidor med inversen får vi:
- j ≡ 2 × 1 (mod 3)
eller
- j ≡ 2 (mod 3)
För att ovanstående ska vara sant: j = 2 + 3 k för något heltal k . Ersätt nu tillbaka till 3 + 4 j och vi får
- x = 3 + 4(2 + 3 k )
Bygga ut:
- x = 11 + 12 k
för att få lösningen
x ≡ 11 (mod 12)
Exempel 2 (En enklare metod)
Även om metoden som användes i det föregående exemplet är sammanhängande, fungerar den inte för alla problem.
Betrakta dessa fyra system av kongruenser:
- x ≡ 1 (mod 2)
- x ≡ 2 (mod 3)
- x ≡ 3 (mod 5)
- x ≡ 4 (mod 11)
För att fortsätta med att hitta ett uttryck som representerar alla lösningar som uppfyller detta system av linjära kongruenser, är det viktigt att veta att a (mod b) har en analog identitet:
- a (mod b) ⇔ b k + a, ∀k ∈ Z, där k är en godtycklig konstant.
PROCEDUR
1. Börja med att skriva om den första kongruensen som en ekvation:
- x = 2a + 1, ∀a ∈ Z
2. Skriv om den andra kongruensen som en ekvation och ställ in ekvationen i det första steget lika med denna ekvation, eftersom x kommer att ersätta x i den andra kongruensen:
- x ≡ 2 (mod 3)
- x = 2a + 1 ≡ 2 (mod 3)
- 2a ≡ 1 (mod 3)
- a ≡ 2 −1 (mod 3)
- a = -1.
Eftersom a måste vara en positiv icke-negativ invers , behöver vi ett positivt a . Således adderar vi vad vår strömmodul är till a, vilket är a = -1 + 3 = 2 .
3. Vi skriver nu om a = 2 i termer av vår nuvarande modul:
- a = 2 (mod 3)
- ∴ a = 3b + 2
4. Vi ersätter nu vårt nuvarande värde på a i vår ekvation som vi hittade i steg 1 med avseende på x:
- x = 2a + 1
- = 2(3b + 2) + 1, ∀b ∈ Z
- = 6b + 5.
∴ x = 6b + 5.
5. Vi ersätter nu vårt nya värde för x med x i vår tredje linjära kongruens, och skriver om 3 (mod 5) till dess ekvivalenta uttryck:
- x ≡ 3 (mod 5)
- = 6b + 5 ≡ 3 (mod 5)
- = 6b + 5 = 5b + 3
- = b = -2.
Eftersom b = -2 adderar vi vår ström till modul till den för att få b = 3.
∴ b = 5c + 3.
6. Vi ersätter återigen vårt nya värde för b i vår ekvation som vi hittade i steg 4 med avseende på x:
- x = 6b + 5
- = 6(5c + 3) + 5
- = 30c + 23
∴ x = 30c + 23, ∀c ∈ Z
7. Vi ersätter nu vårt nya värde för x med x i vår slutliga linjära kongruens, och skriver om 4 (mod 11) till dess ekvivalenta uttryck:
- x ≡ 4 (mod 11)
- = 30c + 18 ≡ 4 (mod 11)
- = 30c + 23 = 11c + 4
- = 19c = -19
- = c = -1.
Lägger vi till vår nuvarande modul till värdet som c representerar, vår nya c = 10.
∴ c = 11d + 10, ∀d ∈ Z.
8. Vårt sista steg är att ersätta c i ekvationen med avseende på x som vi hittade i steg 6:
- x = 30c + 23
- = 30(11d + 10) + 23
- = 330d + 323.
∴ 330d + 323 representerar alla lösningar som uppfyller det system av kongruenser som vi började med.
Kontrollerar vårt arbete
För att kontrollera att vårt svar är korrekt, härleder vi om varje respektive rest är tänkt när vi beräknar 323 av modulo för varje kongruens:
323 ≡ 1 (mod 2)
- 323 = 161 * 2 + 1
323 ≡ 2 (mod 3)
- 323 = 107 * 3 + 2
323 ≡ 3 (mod 5)
- 323 = 64 * 5 + 3
323 ≡ 4 (mod 11)
- 323 = 29 * 11 + 4
En alternativ metod skulle vara att härleda om varje modul delar skillnaden på 323 och varje kongruens respektive rest:
2 | (323 - 1) är sant.
3 | (323 - 2) är sant.
5 | (323 - 3) är sant.
11 | (323 - 4) är sant.
Ett annat sätt att lösa systemet med linjära kongruenser är att använda den kinesiska restsatsen , och det kommer att ge oss samma resultat.
Exempel 3 (Liknande metod som används ovan men med en vridning)
När man löser ett system av linjära kongruenser med den metod som används i exemplet ovan, kommer det att finnas situationer där lösning för en variabel ger en rationell.
Nyckeln till att lösa variabeln är att addera strömmodulen till den andra sidan av ekvationen, tills en multipel av koefficienten för variabeln som löses för
är upphandlad. Här är ett exempel:
- x ≡ 2 (mod 3)
- x ≡ 3 (mod 5)
- x ≡ 2 (mod 7)
PROCEDUR
1. Skriv om den första linjära kongruensen till dess ekvivalenta ekvation:
- x ≡ 2 (mod 3)
- x = 3a + 2, ∀a ∈ Z.
2. Skriv om den andra kongruensen som en ekvation och sätt uttrycket lika med uttrycket som hittades i föregående steg:
- x ≡ 3 (mod 5)
- x = 5a + 3, ∀a ∈ Z
- 3a + 2 = 5a + 3
- -1 = 2a
Det är här metoden som används i exempel 2 verkar ha problem, men jag hittade en lösning: Lägg till vad som än är strömmodulen till den sida av ekvationen där variabeln inte är, tills koefficienten kan dividera den. Anledningen till att vi kan göra detta är på grund av definitionen av en kongruensklass alltså,
3. Lägg till 5, som är vår modul, till -1 för att få:
- -1 + 5 = 4
- 4 = 2a
- a = 2.
4. Skriv om a = 2 som dess ekvivalenta modulära ekvation
- a = 2 blir a = 5b + 2, ∀b ∈ Z.
5. Ersätt vårt nuvarande a i ekvationen som togs fram i steg 1 med avseende på x:
- x = 3a + 2 = 3 (5b + 2) + 2 = 15b + 8.
- ∴ x = 15b + 8.
6. Skriv slutligen om den tredje kongruensen och sätt den lika med ekvationen i föregående steg, och lös för b.
- x ≡ 2 (mod 7) kan skrivas om som x = 7b + 2
Vi har ersatt x
- 15b + 8 = 7b + 2
- 8b = -6
Lägg till vår nuvarande modul, som är 7, till -6, tills en multipel av 8 är tänkt:
- -6 + 7 = 1 + 7 = 8.
Således,
- 8b = 8
- b = 1.
Omskrivning av b i termer av dess modul har vi
- b = 7c + 1, ∀c ∈ Z
7. Ersätt vår nya ekvation b med b i ekvationen med avseende på x vi tänkte på i steg 6:
- x = 15b + 8
- = 15 (7c + 1) + 8
- = 105c + 23
- ∴ x = 105c + 23.
∴ 105c + 23 representerar alla lösningar som uppfyller det system av kongruenser som vi började med.
Kontrollerar vårt arbete
För att kontrollera att vårt svar är korrekt, härleder vi om varje respektive rest är tänkt när vi beräknar 23 med modulo för varje kongruens:
23 ≡ 2 (mod 3)
- 23 = 7 * 3 + 2
23 ≡ 3 (mod 5)
- 23 = 4 * 5 + 3
23 ≡ 2 (mod 7)
- 23 = 3 * 7 + 2
Allmän algoritm
I allmänhet:
- skriv den första ekvationen i dess ekvivalenta form
- ersätt det med nästa
- förenkla, använd den modulära multiplikativa inversen om det behövs
- fortsätt till den sista ekvationen
- tillbaka ersättare, sedan förenkla
- skriv tillbaka i kongruensformen
Om modulerna är coprime ger den kinesiska restsatsen en enkel formel för att erhålla lösningen.