Matematyka.pl

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.

A co tu jest niewiadomą?

Zawsze mamy dane jakieś \(\displaystyle{ n}\) oraz \(\displaystyle{ c}\). Niewiadomymi pozostają wówczas \(\displaystyle{ a}\) i \(\displaystyle{ b}\).

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}\).

Tak wynikało z tych metod, które znalazłem. Tylko nie wiem jak to rozwiązać dla tej jedynki.

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}\).

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.

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.

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.

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

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.