Metoda kolejnych podstawień
W arytmetyce modułowej metoda kolejnych podstawień jest metodą rozwiązywania problemów równoczesnych kongruencji za pomocą definicji równania kongruencji. Jest powszechnie stosowany w przypadkach, gdy nie są spełnione warunki chińskiego twierdzenia o resztach .
Istnieje również niepowiązana metoda analizy numerycznej polegająca na kolejnym podstawieniu, losowy algorytm używany do wyszukiwania pierwiastków , zastosowanie iteracji punktu stałego .
Metoda kolejnych podstawień jest również znana jako podstawienie wsteczne.
Przykłady
Przykład pierwszy
Rozważmy prosty zbiór jednoczesnych kongruencji
- x ≡ 3 (mod 4)
- x ≡ 5 (mod 6)
Teraz, aby x ≡ 3 (mod 4) było prawdziwe, x = 3 + 4 j dla pewnej liczby całkowitej j . Podstaw to w drugim równaniu
- 3+4 j ≡ 5 (mod 6)
ponieważ szukamy rozwiązań obu równań.
Odejmij 3 z obu stron (jest to dozwolone w arytmetyce modularnej)
- 4 j ≡ 2 (mod 6)
Upraszczamy, dzieląc przez największy wspólny dzielnik 4,2 i 6. Dzielenie przez 2 daje:
- 2 j ≡ 1 (mod 3)
Euklidesowa modułowa multiplikatywna odwrotność 2 mod 3 to 2. Po pomnożeniu obu stron przez odwrotność otrzymujemy:
- j ≡ 2 × 1 (mod 3)
Lub
- j ≡ 2 (mod 3)
Aby powyższe było prawdziwe: j = 2 + 3 k dla pewnej liczby całkowitej k . Teraz podstawiamy z powrotem do 3 + 4 j i otrzymujemy
- x = 3 + 4(2 + 3 k )
Zwiększać:
- x = 11 + 12 k
aby uzyskać rozwiązanie
x ≡ 11 (mod 12)
Przykład 2 (prostsza metoda)
Chociaż metoda zastosowana w poprzednim przykładzie jest spójna, nie działa dla każdego problemu.
Rozważ te cztery systemy kongruencji:
- x ≡ 1 (mod 2)
- x ≡ 2 (mod 3)
- x ≡ 3 (mod 5)
- x ≡ 4 (mod 11)
Aby przystąpić do znajdowania wyrażenia reprezentującego wszystkie rozwiązania, które spełniają ten układ kongruencji liniowych, ważne jest, aby wiedzieć, że a (mod b) ma analogiczną tożsamość:
- a (mod b) ⇔ b k + a, ∀k ∈ Z, gdzie k jest dowolną stałą.
PROCEDURA
1. Rozpocznij od przepisania pierwszej kongruencji jako równania:
- x = 2a + 1, ∀a ∈ Z
2. Przepisz drugą kongruencję jako równanie i ustaw równanie znalezione w pierwszym kroku jako równe temu równaniu, ponieważ x zastąpi x w drugiej kongruencji:
- x ≡ 2 (mod 3)
- x = 2a + 1 ≡ 2 (mod 3)
- 2a ≡ 1 (mod 3)
- a ≡ 2 −1 (mod 3)
- a = -1.
Ponieważ a musi być dodatnią, nieujemną odwrotnością , potrzebujemy dodatniego a . W ten sposób dodajemy dowolny nasz aktualny moduł do a, czyli a = -1 + 3 = 2 .
3. Przepiszemy teraz a = 2 pod względem naszego obecnego modułu:
- a = 2 (moda 3)
- ∴ za = 3b + 2
4. Teraz podstawiamy naszą aktualną wartość a do naszego równania, które znaleźliśmy w kroku 1 w odniesieniu do x:
- x = 2a + 1
- = 2(3b + 2) + 1, ∀b ∈ Z
- = 6b + 5.
∴x = 6b + 5.
5. Teraz podstawiamy naszą nową wartość dla x do x w naszej trzeciej kongruencji liniowej i przepisujemy 3 (mod 5) na jego równoważne wyrażenie:
- x ≡ 3 (mod 5)
- = 6b + 5 ≡ 3 (mod 5)
- = 6b + 5 = 5b + 3
- = b = -2.
Ponieważ b = -2 , dodajemy do niego nasz prąd do modułu w celu uzyskania b = 3.
∴ b = 5c + 3.
6. Ponownie podstawiamy naszą nową wartość dla b do naszego równania, które znaleźliśmy w kroku 4 w odniesieniu do x:
- x = 6b + 5
- = 6(5c + 3) + 5
- = 30c + 23
∴ x = 30c + 23, ∀c ∈ Z
7. Teraz podstawiamy naszą nową wartość dla x do x naszej końcowej kongruencji liniowej, przepisując 4 (mod 11) na jej równoważne wyrażenie:
- x ≡ 4 (mod 11)
- = 30c + 18 ≡ 4 (mod 11)
- = 30c + 23 = 11c + 4
- = 19c = -19
- = do = -1.
Dodając nasz obecny moduł do wartości, którą reprezentuje c , nasze nowe c = 10.
∴ do = 11d + 10, ∀d ∈ Z.
8. Naszym ostatnim krokiem jest podstawienie c do równania względem x , które znaleźliśmy w kroku 6:
- x = 30c + 23
- = 30(11d + 10) + 23
- = 330d + 323.
∴ 330d + 323 reprezentuje wszystkie rozwiązania, które spełniają system kongruencji, od którego zaczęliśmy.
Sprawdzanie naszej pracy
Aby sprawdzić, czy nasza odpowiedź jest poprawna, dedukujemy, czy każda odpowiednia reszta jest pomyślana, gdy obliczamy 323 przez modulo każdej kongruencji:
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
Alternatywną metodą byłoby wydedukowanie, czy każdy moduł dzieli różnicę 323 i odpowiednią resztę każdej kongruencji:
2 | (323 - 1) jest prawdziwe.
3 | (323 - 2) jest prawdą.
5 | (323 - 3) jest prawdą.
11 | (323 - 4) jest prawdą.
Innym sposobem rozwiązania układu kongruencji liniowych jest użycie chińskiego twierdzenia o resztach , które da nam ten sam wynik.
Przykład 3 (podobna metoda zastosowana powyżej, ale z niespodzianką)
Podczas rozwiązywania układu kongruencji liniowych metodą zastosowaną w powyższym przykładzie będą sytuacje, w których rozwiązanie dla zmiennej da wynik wymierny.
Kluczem do rozwiązania dla zmiennej jest dodanie aktualnego modułu po drugiej stronie równania, aż do uzyskania wielokrotności współczynnika zmiennej, dla której
jest nabywany. Oto przykład:
- x ≡ 2 (mod 3)
- x ≡ 3 (mod 5)
- x ≡ 2 (mod 7)
PROCEDURA
1. Przepisz pierwszą kongruencję liniową do jej równoważnego równania:
- x ≡ 2 (mod 3)
- x = 3a + 2, ∀a ∈ Z.
2. Przepisz drugą kongruencję jako równanie i ustaw wyrażenie równe wyrażeniu znalezionemu w poprzednim kroku:
- x ≡ 3 (mod 5)
- x = 5a + 3, ∀a ∈ Z
- 3a + 2 = 5a + 3
- -1 = 2a
W tym miejscu metoda zastosowana w przykładzie 2 wydaje się mieć problemy, ale znalazłem rozwiązanie: dodaj dowolny bieżący moduł po stronie równania, po której nie ma zmiennej, dopóki współczynnik nie będzie w stanie go podzielić. Powodem, dla którego możemy to zrobić , jest definicja klasy kongruencji
3. Dodaj 5, czyli nasz moduł, do -1, aby otrzymać:
- -1 + 5 = 4
- 4 = 2a
- za = 2.
4. Przepisz a = 2 jako równoważne równanie modularne
- a = 2 staje się a = 5b + 2, ∀b ∈ Z.
5. Podstawmy nasz prąd a do równania otrzymanego w kroku 1 w odniesieniu do x:
- x = 3a + 2 = 3 (5b + 2) + 2 = 15b + 8.
- ∴x = 15b + 8.
6. Na koniec przepisz trzecią kongruencję i przyrównaj ją do równania otrzymanego w poprzednim kroku, rozwiązując b.
- x ≡ 2 (mod 7) można przepisać jako x = 7b + 2
Zastępując x mamy
- 15b + 8 = 7b + 2
- 8b = -6
Dodaj nasz obecny moduł, który wynosi 7, do -6, aż powstanie wielokrotność 8:
- -6 + 7 = 1 + 7 = 8.
Zatem,
- 8b = 8
- b = 1.
Przepisując b pod względem jego modułu, mamy
- b = 7c + 1, ∀c ∈ Z
7. Zastąp nasze nowe równanie b zamiast b w równaniu względem x, które wymyśliliśmy w kroku 6:
- x = 15b + 8
- = 15 (7c + 1) + 8
- = 105c + 23
- ∴x = 105c + 23.
∴ 105c + 23 reprezentuje wszystkie rozwiązania, które spełniają system kongruencji, od którego zaczęliśmy.
Sprawdzanie naszej pracy
Aby sprawdzić, czy nasza odpowiedź jest poprawna, dedukujemy, czy każda odpowiednia reszta jest pomyślana, gdy obliczamy 23 przez modulo każdej kongruencji:
23 ≡ 2 (mod 3)
- 23 = 7 * 3 + 2
23 ≡ 3 (mod 5)
- 23 = 4 * 5 + 3
23 ≡ 2 (mod 7)
- 23 = 3 * 7 + 2
Algorytm ogólny
Ogólnie:
- napisz pierwsze równanie w jego równoważnej postaci
- zastąp go następnym uproszczeniem,
- w razie potrzeby użyj modułowej odwrotności multiplikatywnej
- kontynuuj do ostatniego równania
- podstawienie wsteczne, a następnie uproszczenie
- przepisać z powrotem w postaci kongruencji
Jeśli moduły są względnie pierwsze , chińskie twierdzenie o resztach daje prosty wzór na uzyskanie rozwiązania.