Liniowe równanie diofantyczne

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
matemix
Użytkownik
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

Post autor: matemix »

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.
Ostatnio zmieniony 7 wrz 2019, o 16:43 przez matemix, łącznie zmieniany 1 raz.
a4karo
Użytkownik
Użytkownik
Posty: 22173
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 38 razy
Pomógł: 3748 razy

Re: Liniowe równanie diofantyczne

Post autor: a4karo »

A co tu jest niewiadomą?
matemix
Użytkownik
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

Post autor: matemix »

Zawsze mamy dane jakieś \(\displaystyle{ n}\) oraz \(\displaystyle{ c}\). Niewiadomymi pozostają wówczas \(\displaystyle{ a}\) i \(\displaystyle{ b}\).
Awatar użytkownika
Gosda
Użytkownik
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

Post autor: Gosda »

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}\).
matemix
Użytkownik
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

Post autor: matemix »

Tak wynikało z tych metod, które znalazłem. Tylko nie wiem jak to rozwiązać dla tej jedynki.
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

Re: Liniowe równanie diofantyczne

Post autor: Premislav »

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}\).
matemix
Użytkownik
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

Post autor: matemix »

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.
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

Re: Liniowe równanie diofantyczne

Post autor: Premislav »

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.
matemix
Użytkownik
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

Post autor: matemix »

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.
Jan Kraszewski
Administrator
Administrator
Posty: 34128
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Re: Liniowe równanie diofantyczne

Post autor: Jan Kraszewski »

matemix pisze: 8 wrz 2019, o 13:18I 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.
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
matemix
Użytkownik
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

Post autor: matemix »

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.
ODPOWIEDZ