Wyznaczyć liczby całkowite

[Honzik18]

Niech \(\displaystyle{ J(1) = 1, J(2n) = 2J(n)- 1, J(2n + 1) = 2J(n) + 1}\) dla \(\displaystyle{ n \ge 1}\). Wyznaczyć liczby
całkowite \(\displaystyle{ x}\) i \(\displaystyle{ y}\) takie, ze \(\displaystyle{ xJ(61) + yJ(63) = NWD(J(61); J(63)).}\)

Wyszło mi
\(\displaystyle{ J(61)= 59}\)
\(\displaystyle{ J(63)=63}\)
\(\displaystyle{ NWD(63,59)=1}\)

\(\displaystyle{ 59x + 63y=1}\)

Co trzeba dalej zrobić?

[Pancernik]

Ja zrobiłem to za pomocą prób i błędów ale wyszło mi \(\displaystyle{ x=-16,y=15}\)
Jak wpadnę jak to zrobić, to dam znać.

[Honzik18]

Tak też można, w notatkach mam, że stosuje się chyba algorytm Euklidesa, dokładnie rozpisuje się tabelkę

x| y | a | b | q | r |
1| 0 |
0| 1 | 63| 59| 1 | 4
?| ? |59 | 4 | 16 | 3
?| ? | 4 | 3 | 1 | 1
?| ? | 3 | 1 | 3 | 0
-| - | 1 | 0

Czyli wychodzi NWD=1. Nie wiem jak się wyznacza x i y, ale liczy się to wierszami, że tam gdzie wyszedł NWD bierze się parametry x i y i podstawia do równania i powinno wyjść. Ktoś ogarnia to?

[yorgin]

Kod: Zaznacz cały

http://www.algorytm.org/algorytmy-arytmetyczne/rozszerzony-algorytm-euklidesa.html

[Honzik18]

Już zrozumiałem Yorgin thx