Diofantiske likninger

[Buzzybi]

Har lenge prøvd å løse denne diofantiske likningen

9cm(x) pluss 13cm(y)er 800 cm

Det er selve utregninga jeg ikke får til..veldig-veldig fint hvis noen kan hjelpe meg.

[dischler]

9 og 13 er relativt primiske (største felles divisor er 1)

Da finnes x og y slik at
9x + 13y = 1
(dette følger fra et eller annet viktig teorem jeg ikke kan navnet på)

x og y kan her finnes fra euklids algoritme slik:

13 = 1*9 + 4
9 = 2*4 + 1

baklengs "nøsting" gir oss da:

1 = 9 - 2*4 = 9 - 2*(13 - 1*9) = = 3*9 + (-2)*13

altså x = 3 og y lik -2.


Dersom de opprinnelige x og y i opgaven din må være positive tall kan du tenke slik:

Vi vet at
3*9 + (-2)*13 = 1

Da er:
3*9 + (-2)*13 + 61*13 = 3*9 + 59*13 = 794
(61 ble valgt fordi det er det største hele tallet som ganget med 13 ikke gjør at vi overstiger 800)

Nå mangler vi bare 6 for å få 800, men det løser vi ved å bruke at:

6(3*9 + (-2)*13) = 6

altså:

(3*9 + 59*13) + 6(3*9 + (-2)*13) = 794 + 6

21*9 + 47*13 = 800

[Buzzy bee]

Tusen, tusen takk!! Nå skjønner jeg oppgaven - det var en lettelse!
Du forklarte det veldig godt. Det var Eukalids algoritme du brukte først. Ha en fin, fin dag!