Citat:
Ursprungligen postat av
P.Ewing33
Har suttit med denna uppgift ett tag men får inte grepp om den.
Ange antalet positiva heltalslösningar, där x och y är udda tal, till ekvationen
17x + 11y = 1000
Får med Euklides algoritm baklänges att x=2000 y=-3000 men det hjälper mig inte.
Tack på förhand!
Du får att
en lösning till den diofantiska ekvationen 17x+11y=1000.
Alla lösningar fås av:
[;(x, y)=(2000+11n, -3000-17n), n\in\mathbb{Z};]
vilket vi kan förenkla till:
[;(x, y)=(9+11m, 77-17m), m\in\mathbb{Z};] genom att sätta 181m=n
Nu måste vi ordna så att vare sig x eller y är negativa, eftersom vi bara söker de positiva heltalslösningarna (som dessutom är udda, men det kommer vi till snart). Vi ser att m kan inte vara negativt, ty då blir x negativt. Vidare kan m inte vara större än 4, för då blir y negativt. Så [;m\in\{0, 1, 2, 3, 4\};] för positiva lösningar. Eftersom vi bara har 5 kandidater är det enkelt att testa var och en och se om både x och y är udda. Annars kan man resonera att endast jämna m kommer att resultera i udda x och udda y. Alltså fås alla lösningar enligt:
[;(x, y)=(9+11m,\,77-17m),\,m\in\{0, 2, 4\};]
Explicit blir dessa lösningar (9, 77), (31, 53) och (53, 19) (om min huvudräkning inte är åt skogen)