nwd - równanie

binio · Post autor: **binio** » 17 maja 2011, o 14:51

Witam! Czy mógł by ktoś opisać jak rozwiązuje się takie równanie według algorytmu Euklidesa. Nie mogę nigdzie znaleźć jak to zrobić. Proszę o pomoc.

\(\displaystyle{ 84x+112y=nwd(84, 112)}\)

Post autor: **Afish** » 17 maja 2011, o 15:04

Nie gwarantuję poprawności.
\(\displaystyle{ nwd(84,112) = 28\\
84x + 112y = 28\\
3x + 4y = 1}\)
A teraz z rozszerzonego algorytmu Euklidesa.

Natasha · Post autor: **Natasha** » 17 maja 2011, o 15:07

Najpierw musisz znaleźć \(\displaystyle{ nwd(84,112)}\)
Najpierw dzielisz z resztą większą liczbę przez mniejszą i zapisujesz wynik
\(\displaystyle{ 112=1\cdot 84+28}\)
Potem dzielimy z resztą poprzedni dzielnik, czyli 84, przez resztę, czyli 28:
\(\displaystyle{ 84=3\cdot 28+0}\), ostatnia niezerowa reszta to 28, więc \(\displaystyle{ nwd(84,112)=28}\)

Teraz próbujemy zapisać korzystajac z naszych równości \(\displaystyle{ 28=112-1\cdot 84=-84+112}\)
\(\displaystyle{ x=-1,y=1}\)

binio · Post autor: **binio** » 17 maja 2011, o 15:16

A skąd wniosek że \(\displaystyle{ -84+112}\) daje nam \(\displaystyle{ x = -1, y = 1}\) bo tego nie rozumiem.

Natasha · Post autor: **Natasha** » 17 maja 2011, o 15:31

mamy \(\displaystyle{ nwd(84,112)=28}\), a \(\displaystyle{ nwd(84,112)=84x+112y}\). Stąd
\(\displaystyle{ 28=-84+112=(-1)\cdot 84+1\cdot 112}\), więc u nas x będzie równe -1, a y=1.

binio · Post autor: **binio** » 18 maja 2011, o 03:39

NOOOOO wielkie dzięki teraz kapuje, a nie mogłem do tego dojść.