Citat:
Ursprungligen postat av Faciteus
Vilket är det minsta naturliga tal, som vid division med 17 lämnar resten 8 och vid division med 6 lämnar resten 4?
Svaret är
Jag antar att det är moduloräkning men vet inte inte hur jag ska börja.
Sätt upp ett ekvationssystem.
Systemet:x ≡ 8 (mod 17)
x ≡ 4 (mod 6)
Systemet har lösning, om och endast om SGD(17,6) = 1 och vi ser att så är fallet, ty 17 är ett primt tal. För att göra det enklare för oss kan vi skriva våra kongruenser i form av likheter och införa en till variabel (parametisering??).
x ≡ 8 (mod 17) ⇔
x = 8+17n
Där n är ett godtyckligt heltal. Vi kan nu göra det samma med den andra ekvationen. Och sedan innan vet vi ju vad x är lika med.
Så vi tittar då på den andra ekvationen och stoppar nu in vad vi vet om x:x ≡ 4 (mod 6) ⇔
8+17n ≡ 4 (mod 6) ⇔
Eftersom x är lika med 8+17n.
2-n ≡ 4 (mod 6) ⇔
Hängde du med på det sista steget där? Jag "modulerade" ner 17 till -1 och 8 till 2. Eftersom dessa tal är kongruenta modulo 6.
2-n-2 ≡ 4-2 (mod 6) ⇔
-n ≡ 2 (mod 6) ⇔
n ≡ -2 (mod 6) ⇔
n ≡ 4 (mod 6) ⇔
n = 4+6k
Vi kan nu gå tillbaka till ekvation 1, och använder det vi vet om n. Vi kan alltså uttrycka x i termer av k. Anledningen till att vi går tillbaka såhär är att vi måste använda argumenten från alla ekvationer för att lösa uppgiften.
Ekvation 1 säger ju att:x = 8+17n ⇔
x = 8+17(4+6k) ⇔
x = 8+17·4+17·6k ⇔
x = 72+102k
Fast vi ville ju veta det minsta talet x. Alltså minimum av x. Min(x) = 72, Min(x) > 0, och det sker när k = 0.
Svar: 72