Metoda postupné substituce - Method of successive substitution - Wikipedia

v modulární aritmetika, metoda postupné substituce je metoda řešení problémů simultánní kongruence pomocí definice rovnice kongruence. Běžně se používá v případech, kdy jsou splněny podmínky EU Čínská věta o zbytku nejsou spokojeni.

Existuje také nesouvisející metoda numerické analýzy postupné substituce, a randomizovaný algoritmus používá kořenový nález, aplikace iterace s pevným bodem.

Metoda postupné substituce je také známá jako zpětná substituce.

Příklady

Příklad jedna

Zvažte jednoduchou sadu simultánních kongruencí

X ≡ 3 (mod 4)
X ≡ 5 (mod 6)

Nyní, pro X ≡ 3 (mod 4), aby to byla pravda, X = 3 + 4j pro celé číslo j. Nahraďte to ve druhé rovnici

3+4j ≡ 5 (mod 6)

protože hledáme řešení oba rovnice.

Odečtěte 3 od obou stran (to je povoleno v modulární aritmetice)

4j ≡ 2 (mod 6)

Zjednodušíme to dělením největší společný dělitel 4,2 a 6. Dělení 2 výnosy:

2j ≡ 1 (mod 3)

Euklidovský modulární multiplikativní inverzní 2 mod 3 je 2. Po vynásobení obou stran inverzí získáme:

j ≡ 2 × 1 (mod 3)

nebo

j ≡ 2 (mod 3)

Aby to bylo pravdivé: j = 2 + 3k pro celé číslo k. Nyní střídejte zpět do 3 + 4j a získáme

X = 3 + 4(2 + 3k)

Rozšířit:

X = 11 + 12k

získat řešení

X ≡ 11 (mod 12)

Příklad 2 (jednodušší metoda)

Ačkoli je metoda použitá v předchozím příkladu koherentní, nefunguje u každého problému.

Zvažte tyto čtyři systémy shody:

  • x ≡ 1 (mod 2)
  • x ≡ 2 (mod 3)
  • x ≡ 3 (mod 5)
  • x ≡ 4 (mod 11)

Abychom mohli pokračovat v hledání výrazu, který představuje všechna řešení, která splňují tento systém lineárních shod, je důležité vědět, že a (mod b) má obdobnou identitu:

    • a (mod b) ⇔ bk + a, ∈k ∈ Z, kde k je libovolná konstanta.

POSTUP

1. Začněte přepsáním první kongruence jako rovnici:

  • x = 2a + 1, ∀a ∈ Z

2. Přepište druhou kongruenci jako rovnici a rovnici nalezenou v prvním kroku nastavte na tuto rovnici, protože X nahradí x ve druhé kongruenci:

  • x ≡ 2 (mod 3)
  • x = 2a + 1 ≡ 2 (mod 3)
  • 2a ≡ 1 (mod 3)
  • a ≡ 2⁻¹ (mod 3)
  • a = -1.

Protože A musí být pozitivní nezáporná inverze, potřebujeme pozitivní A. Přidáme tedy jakýkoli náš aktuální modul k a, což je a = -1 + 3 = 2.

3. Nyní přepisujeme a = 2 z hlediska našeho aktuálního modulu:

  • a = 2 (mod 3)
  • ∴ a = 3b + 2

4. Nyní dosadíme naši současnou hodnotu A do naší rovnice, ve které jsme našli krok 1 s ohledem na X:

  • x = 2a + 1
  • = 2 (3b + 2) + 1, ∀b ∈ Z.
  • = 6b + 5.

∴ x = 6b + 5.

5. Nyní nahrazujeme naši novou hodnotu X do x v naší třetí lineární kongruenci a přepsat 3 (mod 5) na jeho ekvivalentní výraz:

  • x ≡ 3 (mod 5)
  • = 6b + 5 ≡ 3 (mod 5)
  • = 6b + 5 = 5b + 3
  • = b = -2.

Protože b = -2, přidáme k němu náš proud do modulu, abychom získali b = 3.

∴ b = 5c + 3.

6. Opět nahrazujeme naši novou hodnotu b do naší rovnice, ve které jsme našli krok 4 s ohledem na X:

  • x = 6b + 5
  • = 6 (5c + 3) + 5
  • = 30c + 23

∴ x = 30c + 23, ∀c ∈ Z

7. Nyní nahrazujeme naši novou hodnotu X do x naší konečné lineární kongruence, přepsání 4 (mod 11) na jeho ekvivalentní výraz:

  • x ≡ 4 (mod 11)
  • = 30c + 18 ≡ 4 (mod 11)
  • = 30c + 23 = 11c + 4
  • = 19c = -19
  • = c = -1.

Přidáním našeho aktuálního modulu k hodnotě, která C představuje náš nový C = 10.

∴ c = 11d + 10, ∀d ∈ Z.

8. Naším posledním krokem je nahrazení C do rovnice vzhledem k x ve kterém jsme našli krok 6:

  • x = 30c + 23
  • = 30 (11 d + 10) + 23
  • = 330 d + 323.

∴ 330d + 323 představuje všechna řešení, která splňují systém shody, s nimiž jsme začali.

Kontrola naší práce

Abychom zkontrolovali, zda je naše odpověď správná, odvodíme, zda je každý příslušný zbytek koncipován, když počítáme 323 modulo každé kongruence:

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

Alternativní metodou by bylo odvodit, zda každý modul rozdělí rozdíl 323 a příslušný zbytek každé kongruence:

2 | (323 - 1) je pravda.

3 | (323 - 2) je pravda.

5 | (323 - 3) je pravda.

11 | (323 - 4) je pravda.

Dalším způsobem, jak vyřešit systém lineárních kongruencí, je použití Čínská věta o zbytku a přinese nám stejný výsledek.

Příklad 3 (Podobná metoda použitá výše, ale s twistem)

Při řešení systému lineárních kongruencí metodou použitou ve výše uvedeném příkladu nastanou situace, kdy řešení pro proměnnou bude racionální.

Klíčem k řešení proměnné je přidání aktuálního modulu na druhou stranu rovnice, dokud se násobek koeficientu proměnné, který se řeší pro

je obstaráno. Zde je příklad:

  • x ≡ 2 (mod 3)
  • x ≡ 3 (mod 5)
  • x ≡ 2 (mod 7)

POSTUP

1. Přepište první lineární kongruenci na její ekvivalentní rovnici:

  • x ≡ 2 (mod 3)
  • x = 3a + 2, ∀a ∈ Z.

2. Přepište druhou kongruenci jako rovnici a nastavte výraz rovný výrazu nalezenému v předchozím kroku:

  • x ≡ 3 (mod 5)
  • x = 5a + 3, ∀a ∈ Z
  • 3a + 2 = 5a + 3
  • -1 = 2a

To je místo, kde se zdá, že metoda použitá v příkladu 2 má problémy, ale našel jsem řešení: Přidejte jakýkoli aktuální modul na stranu rovnice, kde proměnná není, dokud ji koeficient nedokáže rozdělit. Důvod, proč to můžeme udělat, je kvůli definici a třída shody Tím pádem,

3. Přidejte 5, což je náš modul, k -1, abyste získali:

  • -1 + 5 = 4
  • 4 = 2a
  • a = 2.

4. Přepište a = 2 jako ekvivalentní modulární rovnice

  • a = 2 se stává a = 5b + 2, ∀b ∈ Z.

5. Nahraďte naše aktuální A do rovnice získané v krok 1 vzhledem k x:

  • x = 3a + 2 = 3 (5b + 2) + 2 = 15b + 8.
  • ∴ x = 15b + 8.

6. Nakonec přepište třetí kongruenci a nastavte ji na rovnici vzniklou v předchozím kroku, řešení pro b.

  • x ≡ 2 (mod 7) lze přepsat jako x = 7b + 2

Nahrazením pro x, máme

  • 15b + 8 = 7b + 2
  • 8b = -6

Přidejte náš aktuální modul, který je 7, až -6, dokud nebude vytvořen násobek 8:

  • -6 + 7 = 1 + 7 = 8.

Tím pádem,

  • 8b = 8
  • b = 1.

Přepisujeme b z hlediska jeho modulu, máme

  • b = 7c + 1, ∀c ∈ Z

7. Nahraďte naši novou rovnici b pro b v rovnici s ohledem na x jsme počali v krok 6:

  • x = 15b + 8
  • = 15 (7c + 1) + 8
  • = 105c + 23
  • ∴ x = 105c + 23.

∴ 105c + 23 představuje všechna řešení, která splňují systém shody, s nimiž jsme začali.

Kontrola naší práce

Abychom zkontrolovali, zda je naše odpověď správná, odvodíme, zda je každý příslušný zbytek koncipován, když vypočítáme 23 modulo každé kongruence:

23 ≡ 2 (mod 3)

  • 23 = 7 * 3 + 2

23 ≡ 3 (mod 5)

  • 23 = 4 * 5 + 3

23 ≡ 2 (mod 7)

  • 23 = 3 * 7 + 2

Obecný algoritmus

Obecně:

  • napište první rovnici v ekvivalentní formě
  • nahradit ji do další
  • pokračujte až do poslední rovnice
  • zpět nahradit, pak zjednodušit
  • přepsat zpět ve formě shody

Pokud jsou moduly coprime, Čínská věta o zbytku dává přímý vzorec pro získání řešení.

Viz také

externí odkazy