Liniowe równanie diofantyczne
-
- Użytkownik
- Posty: 465
- Rejestracja: 10 cze 2008, o 19:38
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 12 razy
- Pomógł: 1 raz
Liniowe równanie diofantyczne
Jak znajdować rozwiązania takich równań:
\(\displaystyle{ n^{y} \cdot a - 2^{x+y} \cdot b = c}\)
\(\displaystyle{ x}\), \(\displaystyle{ y}\) to liczby naturalne, większe od zera, zaś \(\displaystyle{ n}\) to liczba nieparzysta. A \(\displaystyle{ c}\) jest zawsze dane i jest taką liczbą, że równanie ma rozwiązania, co więcej \(\displaystyle{ a}\) nigdy nie będzie większe niż \(\displaystyle{ 2^{x+y}}\). Na przykład:
\(\displaystyle{ 243 \cdot a - 256 \cdot b = 29}\)
albo
\(\displaystyle{ 243 \cdot a - 256 \cdot b = 45}\)
Wiem, że istnieją metody rozwiązywania takich równań, ale te, które znalazłem opierały się na tym, że współczynniki mają jakiś wspólny dzielnik większy od \(\displaystyle{ 1}\). W tym równaniu nie mają nigdy.
\(\displaystyle{ n^{y} \cdot a - 2^{x+y} \cdot b = c}\)
\(\displaystyle{ x}\), \(\displaystyle{ y}\) to liczby naturalne, większe od zera, zaś \(\displaystyle{ n}\) to liczba nieparzysta. A \(\displaystyle{ c}\) jest zawsze dane i jest taką liczbą, że równanie ma rozwiązania, co więcej \(\displaystyle{ a}\) nigdy nie będzie większe niż \(\displaystyle{ 2^{x+y}}\). Na przykład:
\(\displaystyle{ 243 \cdot a - 256 \cdot b = 29}\)
albo
\(\displaystyle{ 243 \cdot a - 256 \cdot b = 45}\)
Wiem, że istnieją metody rozwiązywania takich równań, ale te, które znalazłem opierały się na tym, że współczynniki mają jakiś wspólny dzielnik większy od \(\displaystyle{ 1}\). W tym równaniu nie mają nigdy.
Ostatnio zmieniony 7 wrz 2019, o 16:43 przez matemix, łącznie zmieniany 1 raz.
-
- Użytkownik
- Posty: 465
- Rejestracja: 10 cze 2008, o 19:38
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 12 razy
- Pomógł: 1 raz
Re: Liniowe równanie diofantyczne
Zawsze mamy dane jakieś \(\displaystyle{ n}\) oraz \(\displaystyle{ c}\). Niewiadomymi pozostają wówczas \(\displaystyle{ a}\) i \(\displaystyle{ b}\).
- Gosda
- Użytkownik
- Posty: 340
- Rejestracja: 29 cze 2019, o 19:46
- Płeć: Mężczyzna
- Lokalizacja: Oulu
- Podziękował: 42 razy
- Pomógł: 60 razy
Re: Liniowe równanie diofantyczne
Możesz najpierw rozwiązać równanie \(\displaystyle{ A \cdot a + B \cdot b = 1}\), a następnie przemnożyć otrzymane rozwiązanie przez \(\displaystyle{ 45}\).
- Premislav
- Użytkownik
- Posty: 15688
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Re: Liniowe równanie diofantyczne
Ponieważ \(\displaystyle{ \left(n^{y}, 2^{x+y}\right)=1}\) dla dowolnego \(\displaystyle{ n}\) nieparzystego, więc korzystając z rozszerzonego algorytmu Euklidesa można wyznaczyć takie \(\displaystyle{ s,t\in \mathbb{Z}}\), że \(\displaystyle{ s\cdot n^y+t\cdot 2^{x+y}=1}\), po zrobieniu tego można zauważyć, że także dla dowolnego \(\displaystyle{ m\in \mathbb{Z}}\) jest wówczas \(\displaystyle{ \left(s+m\cdot 2^{x+y}\right)\cdot n^y+\left(t-m\cdot n^y\right)\cdot 2^{x+y}=1}\)
i dobrać takie \(\displaystyle{ m}\), żeby znak odpowiednich wyrażeń był właściwy. No a na koniec mnożysz to przez \(\displaystyle{ c}\).
i dobrać takie \(\displaystyle{ m}\), żeby znak odpowiednich wyrażeń był właściwy. No a na koniec mnożysz to przez \(\displaystyle{ c}\).
-
- Użytkownik
- Posty: 465
- Rejestracja: 10 cze 2008, o 19:38
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 12 razy
- Pomógł: 1 raz
Re: Liniowe równanie diofantyczne
Nie rozumiem tego algorytmu. Wyznaczenie reszt jest łatwe, ale poskładanie tego do kupy nie ma ładu, ani składu
\(\displaystyle{ 256}\) i \(\displaystyle{ 243}\) daje \(\displaystyle{ 1 \cdot 243 + 13}\)
\(\displaystyle{ 243}\) i \(\displaystyle{ 13}\) daje \(\displaystyle{ 18 \cdot 13 + 9}\)
\(\displaystyle{ 13}\) i \(\displaystyle{ 9}\) daje \(\displaystyle{ 1 \cdot 9 + 4}\)
\(\displaystyle{ 9}\) i \(\displaystyle{ 4}\) daje \(\displaystyle{ 2 \cdot 4 + 1}\)
\(\displaystyle{ 4}\) i \(\displaystyle{ 1}\) daje \(\displaystyle{ 4 \cdot 1 + 0}\)
I co dalej?
\(\displaystyle{ 1 = 9-2 \cdot 4 = 9 - 2 \cdot (13-1 \cdot 9) = 9 - 2 \cdot (13-1 \cdot (243-18 \cdot 13)) = 9 - 2 \cdot (13-1 \cdot (243-18 \cdot (256-1 \cdot 243)))}\)
Niczego to nie wnosi. Istnieje jakaś procedura, która pozwala to uporządkować, chyba. Tylko jak ona wygląda? O ile w ogóle istnieje? Bo takie banalne przypadki i przykłady, których jest kilka w internecie sprawdzą się, dopóki będziemy mieli do czynienia z małymi liczbami, a ja chcę rozwiązywać takie równania automatycznie dla dużych liczb. Program nie będzie w stanie się zastanowić gdzie co podstawić i co gdzie lepiej pasuje.
\(\displaystyle{ 256}\) i \(\displaystyle{ 243}\) daje \(\displaystyle{ 1 \cdot 243 + 13}\)
\(\displaystyle{ 243}\) i \(\displaystyle{ 13}\) daje \(\displaystyle{ 18 \cdot 13 + 9}\)
\(\displaystyle{ 13}\) i \(\displaystyle{ 9}\) daje \(\displaystyle{ 1 \cdot 9 + 4}\)
\(\displaystyle{ 9}\) i \(\displaystyle{ 4}\) daje \(\displaystyle{ 2 \cdot 4 + 1}\)
\(\displaystyle{ 4}\) i \(\displaystyle{ 1}\) daje \(\displaystyle{ 4 \cdot 1 + 0}\)
I co dalej?
\(\displaystyle{ 1 = 9-2 \cdot 4 = 9 - 2 \cdot (13-1 \cdot 9) = 9 - 2 \cdot (13-1 \cdot (243-18 \cdot 13)) = 9 - 2 \cdot (13-1 \cdot (243-18 \cdot (256-1 \cdot 243)))}\)
Niczego to nie wnosi. Istnieje jakaś procedura, która pozwala to uporządkować, chyba. Tylko jak ona wygląda? O ile w ogóle istnieje? Bo takie banalne przypadki i przykłady, których jest kilka w internecie sprawdzą się, dopóki będziemy mieli do czynienia z małymi liczbami, a ja chcę rozwiązywać takie równania automatycznie dla dużych liczb. Program nie będzie w stanie się zastanowić gdzie co podstawić i co gdzie lepiej pasuje.
- Premislav
- Użytkownik
- Posty: 15688
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Re: Liniowe równanie diofantyczne
No jeżeli na przykładach nie widzisz jak to działa, to trudno, ja tłumaczyć nie umiem. Skoro chodzi o program, to wpisz sobie w wyszukiwarkę „extended euclidean algorithm implementation" albo coś w tym stylu i narciarz.
-
- Użytkownik
- Posty: 465
- Rejestracja: 10 cze 2008, o 19:38
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 12 razy
- Pomógł: 1 raz
Re: Liniowe równanie diofantyczne
Ok, dzięki Będę szukał takich przykładów, w których jest to wytłumaczone albo sam znajdę algorytm stosowania tego algorytmu, co zajmie mi pewnie znacznie dłużej. Przykłady w internecie są po prostu niejasne i niejednoznaczne.
-
- Administrator
- Posty: 34342
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 3 razy
- Pomógł: 5204 razy
Re: Liniowe równanie diofantyczne
Ależ wnosi, ale tylko pod warunkiem, że wiesz, do czego zmierzasz. A tego na razie - jak widać - nie wiesz.
Chcesz otrzymać rozwiązanie równania \(\displaystyle{ 256x+243y=1}\) w liczbach całkowitych. Korzystając z Algorytmu Euklidesa odwracasz rachunki:
\(\displaystyle{ 1 = 9-2 \cdot 4 = 9 - 2 \cdot (13-1 \cdot 9)=3\cdot 9-2\cdot 13=3\cdot (243-18\cdot13)-2\cdot 13=\\=3\cdot 243-56\cdot 13=3\cdot 243-56\cdot(256-243)=-56\cdot 256+59\cdot 243.}\)
JK
-
- Użytkownik
- Posty: 465
- Rejestracja: 10 cze 2008, o 19:38
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 12 razy
- Pomógł: 1 raz
Re: Liniowe równanie diofantyczne
Wiem do czego zmierzam, ale to wcale nie pomogło. W każdym razie chwilę przed Tobą w końcu uzyskałem to rozwiązanie. I poukładałem sobie algorytm realizacji tego algorytmu. Szkoda, że internetowe poradniki nie zapisują go jawnie. Może ja w takim razie zapiszę, gdyby ktoś czytał ten wątek post factum.
1. Jak już powyliczamy te reszty, porządkujemy wyrażenia według reszt:
A: \(\displaystyle{ 13=256-243}\)
B: \(\displaystyle{ 9=243-18\cdot 13}\)
C: \(\displaystyle{ 4=13-9}\)
D: \(\displaystyle{ 1=9-2 \cdot 4}\)
2. Następnie bierzemy ostatnie równanie i podstawiamy do niego kolejne poziomy, skracając wszystko co się da po drodze:
Poziom D:
\(\displaystyle{ 1=9-2 \cdot 4}\)
Poziom C:
\(\displaystyle{ 1=9-2 \cdot (13-9) = 3 \cdot 9 - 2 \cdot 13}\)
Poziom B:
\(\displaystyle{ 1 = 3 \cdot 9 - 2 \cdot 13 = 3 \cdot (243-18 \cdot 13) - 2 \cdot 13 = 3 \cdot 243 - 56 \cdot 13}\)
Poziom A:
\(\displaystyle{ 1 = 3 \cdot 243 - 56 \cdot 13 = 3 \cdot 243 - 56 \cdot (256-243) = 59 \cdot 243 -56 \cdot 256}\)
I mamy rozwiązanie. Dalej już jest łatwo. I to jest rozpisane jawnie, gdzie, kiedy i co podstawiamy.
1. Jak już powyliczamy te reszty, porządkujemy wyrażenia według reszt:
A: \(\displaystyle{ 13=256-243}\)
B: \(\displaystyle{ 9=243-18\cdot 13}\)
C: \(\displaystyle{ 4=13-9}\)
D: \(\displaystyle{ 1=9-2 \cdot 4}\)
2. Następnie bierzemy ostatnie równanie i podstawiamy do niego kolejne poziomy, skracając wszystko co się da po drodze:
Poziom D:
\(\displaystyle{ 1=9-2 \cdot 4}\)
Poziom C:
\(\displaystyle{ 1=9-2 \cdot (13-9) = 3 \cdot 9 - 2 \cdot 13}\)
Poziom B:
\(\displaystyle{ 1 = 3 \cdot 9 - 2 \cdot 13 = 3 \cdot (243-18 \cdot 13) - 2 \cdot 13 = 3 \cdot 243 - 56 \cdot 13}\)
Poziom A:
\(\displaystyle{ 1 = 3 \cdot 243 - 56 \cdot 13 = 3 \cdot 243 - 56 \cdot (256-243) = 59 \cdot 243 -56 \cdot 256}\)
I mamy rozwiązanie. Dalej już jest łatwo. I to jest rozpisane jawnie, gdzie, kiedy i co podstawiamy.