Euklides algoritm baklängdes
Beräkna sgd(504,301) med hjälp av Euklides algoritm och bestäm alla heltal x och y sådana att 504x + 301y = sgd(504,301)
med Euklides algoritm får vi
504 = 1*301 + 203
301 = 1* 203 + 8
203 = 25*8 + 3
25 = 3*8 +1
sgd(504,301) = 1
vi ska lösa ekvationen 504x + 301y = 1
om vi går baklänges får vi
1 = 25 -(8*3) = 25-(8*(203-(25*8)))
= 25 - (8*(203-(25*(301-203)))
= 25 - (8*(203-(25*(301*(504-301))))
blir ganska snurrig här och vet inte hur ska gå vidare
kanske
25 -(8*(203-(25*(301*203)
25 - 8*203 - 25*301 -25*203
alltså
-33*203 -25*301
Jo, det är "bara" att förenkla och behålla de två intressanta talen hela tiden. Jag brukar göra det ett steg i taget, inte allt på en gång.
Laguna skrev:Jo, det är "bara" att förenkla och behålla de två intressanta talen hela tiden. Jag brukar göra det ett steg i taget, inte allt på en gång.
märkte att jag gjorde ett stort misstag då det ska vara 301 = 203*1 + 98 men stämmer det att man går baklänges så som jag har skrivit?
