matematikk.net

1)Finn et negativt heltall x som tilfredsstiller kongruensen

2008 x [symbol:identisk] 1(mod 12345)

Fasiten sier:

x = 1912 - 12345 = -10 433:

Hvordan i all verden regner man ut dette ?

2)Finn et positivt heltall y som tilfredsstiller kongruensen

12345y [symbol:identisk] 1(mod 2008):

Fasiten sier:

y = -311 + 2008 = 1697

Hadde vært kjempebra om noen kunne vise meg utregningen som gjør at man kommer frem til de fasitsvarene !

Utregninga kan du gjøre sjøl, alt du trenger er Euklids algoritme. Hvis du bruker denne på 2008 og 12345, finner du at disse er koprime. Derfra kan du jobbe deg baklengs opp til å skrive gcd(2008,12345)=a*2008+b*12345 der a og b er heltall. Ei utdypning av dette står i mange tallteoriintroduksjonsbøker.

Satt og prøvde og kom frem til gcd=1.
Hva skal jeg så gjøre videre ?

1= a x 2008 + b x 12345 sier meg jo ikke mye mer

hvordan skal jeg regne ut a og b ?

Se for eksempel eksempel 3.9 på side 18 her: http://www.uio.no/studier/emner/matnat/ ... ll4000.pdf