matematikk.net

Hei,

Har litt vanskelig for å forstå hvordan jeg skal løse følgende oppgave:
"Bruk Euklids utvidede algoritme til å finne en løsning på likningene. gcd(4386, 47874) = 4386 * X + 47874 * Y.

Har så langt regnet ut gcd(4386, 47874):
47874 = 4386 * 10 + 4014
4386 = 4014 * 1 + 372
4014 = 372 * 10 + 294
372 = 294 * 1 + 78
294 = 78 * 3 + 60
78 = 60 * 1 + 18
60 = 18 * 3 + 6
18 = 6 * 3 + 0

Og dette er hva jeg har så langt med den utvidede algoritmen:
6 = 60 - 18 * 3
6 = 60 - (78 - 60 * 1) * 3
6 = -78 * 3 + (294 - 78 * 3) * 4
6 = 294...?

Her stopper det altså. Er noen som kan hjelpe meg på vei?

Hvorfor stopper det opp? Det virker jo som om du har forstått poenget her. Det er bare å fortsette på akkurat samme måte. Det er veldig lett å gjøre regnefeil, riktignok.