Kongruens

x ≡ 3 mod 17
x ≡ 2 mod 10

Någon som kan förklara hur man löser denna kongruens system ?

steg för steg

Eftersom 17 och 10 är relativt prima ger kinesiska restsatsen att det finns en unik lösning modulu 170(=17*10)

Antingen gissar man fram denna, eller så plockar man fram en lösning till 17a+3=10b+2 <=> 10b-17a=1 med Euklides algoritm.

hmm...
17 = 1*10 + 7 <=> 7 = 17 + 10*(-1)
10 = 1*7 + 3 <=> 3 = 10 + 7*(-1)
7 =2*3 + 1 <=> 1 = 7 + 3*(-2)

1 = 7 + 3*(-2) = 7 + (10 + 7*(-1))*(-2) = 7*3 + 10*(-2) =
= (17 + 10*(-1))*3 + 10*(-2) = 17*3 + 10*(-5)


1 = 17*3 + 10*(-5)
1 = 17*a + 10*b

a=3
b=-5

Hur gör jag härifrån ?

x ≡ 3 mod 17 säger att x = 17m + 3 för något heltal m.
x ≡ 2 mod 10 säger att x = 10n + 2 för något heltal n.

Dessa tillsammans ger 17m + 3 = 10n + 2, dvs 10n - 17m = 1 för några heltal m, n.
Denna ekvation kanske du klarar av att lösa?

Jag får ju ut att:
m=3
n=-5
1 = 17*3 + 10*(-5)
men har ingen aning hur jag ska göra nu

Du har hittat en lösning till ekvationen 10n - 17m = 1. Kan du hitta samtliga lösningar?

har ingen aning hur man gör

Du har hittat en partikulärlösning, n = -5, m = -3.
Lägg sedan till godtyckligt antal homogenlösningar: n = 17k, m = 10k.
Samtliga lösningar ges därför av n = -5 + 17k, m = -3 + 10k.

Kan du nu få fram x?

Tyvärr, så har jag ingen aning hur jag ska göra,

x = 17m + 3
x = 10n + 2
n = -5 + 17k, m = -3 + 10k

ah, förstår inte riktigt hur

Om x = 17m + 3 och m = -3 + 10k, vad blir då x (uttryckt i k)?

17*(-3 + 10k) + 3 =
x = -48 + 170k

tusen tack för förklaring

hmm.. kollade facit, står 122 + 170n

vad gick fel ?