system av kongurenser

[Nebuchadnezzar]

Lurer litt på hvor feilen min er =)

Skal løse systemet

[tex]2x \equiv 3 \pmod{5}[/tex]
[tex]4x \equiv 2 \pmod{6}[/tex]
[tex]3x \equiv 2 \pmod{7}[/tex]

Lurer også litt på hva jeg skal skrive mellom overgangene mine. Så kan noen si om overgangene mine ser logiske ut, og om jeg regner rett? Dette burde jo være rimelig enkelt :p

Begynner med å skrive om den første kongurensen.

[tex]2x \equiv 3 \pmod{5}[/tex]
[tex]2x \equiv 8 \pmod{5}\quad[/tex] siden [tex]\quad 8 \equiv 3 \pmod{5}[/tex]

Dette gir oss

[tex]x \equiv 4 \pmod{5}[/tex]
[tex]x \equiv -1 \pmod{5}[/tex]

Siden [tex]\gcd(2,5)=1[/tex] og at [tex]-1 \equiv 4 \pmod{5}[/tex]

Så tar vi for oss neste likning

[tex]4x \equiv 2 \pmod{6}[/tex]
[tex]2x \equiv 1 \pmod{3}[/tex]

Siden [tex]\gcd(4,2)=2[/tex] og [tex]6 \mid 2[/tex]

Som igjen gir

[tex]2x \equiv 4 \pmod{3}[/tex]
[tex] x \equiv 2 \pmod{3}[/tex]
[tex] x \equiv -1 \pmod{3}[/tex]

Siden [tex]\gcd(2,3)=1[/tex] og at [tex]-1 \equiv 2 \pmod{3}[/tex]

På siste likning får vi mye det samme...

[tex]3x \equiv 2 \pmod{7}[/tex]
[tex]3x \equiv 9 \pmod{7}[/tex]
[tex] x \equiv 3 \pmod{7}[/tex]

Siden [tex]2 \equiv 9 \pmod{7}[/tex] og [tex]\gcd(3,7)=1[/tex]

Endelig så har vi omformet likningsystemet til

[tex]x \equiv -1 \pmod{5}[/tex]
[tex]x \equiv -1 \pmod{3}[/tex]
[tex]x \equiv 3 \pmod{7}[/tex]

Tror jeg har gjort en feil til nå, lurer også litt på hva den beste måten videre er.

Bokmetoden er jeg ikke så glad i , og ikke mye vits å regne videre om det jeg har gjort til nå er feil

Første likning gir

[tex]x = 5t - 1 [/tex]

men ja...

[Fibonacci92]

Ser riktig ut.

Altså, av de metodene jeg kan har du 3 muligheter:

1) Solve by inspection
2) Bokmetoden
3) Skrive om x = -1 mod 5 til x = 5k -1 og sette inn i de andre kongruensene for så å gjenta prosessen til du har gjennomgått alle kongruensene. Denne metoden blir forøvrig også beskrevet i boken.

[Nebuchadnezzar]

Boken sier jo at løsningene er

[tex]x \equiv 59,164 \pmod{210}[/tex]

Men med forkortingen min av andre kongurensen får jo jeg maks [tex]x_1,x_2 \pmod{105}[/tex]

Altså om jeg prøver meg på innsetningsmetoden:

første likning gir

[tex]x = 5t - 1 [/tex]

innsatt i andre

[tex]5t - 1 \equiv -1 \pmod{3}[/tex]
[tex]5t \equiv 0 \pmod{3}[/tex]
[tex] t \equiv 0 \pmod{3}[/tex] siden [tex]\gcd(5,3)=1[/tex]
[tex] t = 3u [/tex]
Gir oss at
[tex]x = 15u - 1 [/tex]

Innsatt i tredje og siste

[tex]15u - 1 \equiv 3 \pmod{7}[/tex]
ekvivalent med
[tex]15u = 2 + 7s[/tex]

Setter vi dette inn i første får vi

[tex]x = (2 + 7s) - 1 = 7s + 1[/tex]
Altså blir løsningen

[tex]x = 7s + 1 \pmod{105}[/tex]

Stemmer jo ikke? Jeg får da mange flere løsninger enn 2 her?

[Fibonacci92]

Når du tar overgangen fra mod 6 til mod 3 får du at x = -1 mod 3

Dette resultatet må settes inn igjen i mod 6 uttrykket ditt (litt upresist, men håper du forstår)

Da ser du at både 2= -1 mod 3 og 5 = -1 mod 3,men 2 [symbol:ikke_lik] 5 mod 6. Det er her du må være forsiktig og grunnet til at fasiten kommer med to løsninger.

EDIT: Se forøvrig Theroem 4.7, s.76

[Fibonacci92]

For å utdype litt. Se på beviset og premissene i Theorem 4.8

Vi får to ulike ligningssystemer:

x = -1 mod 5
x = 2 mod 6
x = 3 mod 7

x = -1 mod 5
x = 5 mod 6
x = 3 mod

Hvert av ligningsssytemene oppfyller nå kravene for at de skal ha en unik løsning modulo 5*6*7, som du finner ved å bruke den metoden de utvikler.

[Vektormannen]

Ser ut som det skjer en fortegnsfeil i [tex]15u - 1 \equiv 3[/tex], dette blir jo til [tex]15u \equiv 4[/tex].

Det blir vel heller ikke riktig å bytte ut 15u med 7s+2 (eller 7s+4 som det ville blitt uten den fortegnsfeilen), for da vil jo x kun oppfylle den ene kongruensen modulo 7, mens de andre ikke er oppfylt lenger? Du må vel fortsette i samme stil som du har gjort i de ovenfor, dvs:

[tex]15u \equiv 4[/tex]

[tex]14u + u \equiv 4[/tex]

[tex]u \equiv 4[/tex]

(Alt modulo 7)

som gir [tex]u = 7v + 4[/tex] og videre [tex]x = 15u-1 = 15(7v+4) - 1 = 105 + 59[/tex]

[Fibonacci92]

Dessuten:
"
Innsatt i tredje og siste

15u - 1 \equiv 3 \pmod{7}
ekvivalent med
15u = 2 + 7s "

Her fjerner du jo alt du har "bygget opp".

Det jeg tenker at er fornuftig å gjøre er

15u -1 = 3 mod 7
15u = 4 mod 7
15u - 2*7u = 4 mod 7
u = 4 mod 7

u = 7s +4

Så setter vi inn i det foregående.

x = 15u - 1 = 15(7s +4) - 1 = 105 s +59.

Nå ser du kanskje at mod 210 blir løsningene 59 og 164.

EDIT: Eller det vektormannen sa, og forøvrig beklager jeg at jeg har skrevet så mange poster.

[Nebuchadnezzar]

Ny oppgave, går akkuratt på det samme =)

Vil bare se omjeg har forstått dette. Gjorde noen dumme feil på slutten, men jeg tror jeg forstår dette nå ^^

[tex]x \equiv 5 \pmod{6}[/tex]
[tex]x \equiv 5 \pmod{13}[/tex]
[tex]x \equiv 4 \pmod{5}[/tex]

Dette er ekvivalent med

[tex]x \equiv -1 \pmod{6}[/tex]
[tex]x \equiv 5 \pmod{13}[/tex]
[tex]x \equiv -1 \pmod{5}[/tex]

Øverste gir

[tex]x = 6t - 1[/tex]

Innsatt i nederste

[tex]6t - 1 \equiv -1 \pmod{5}[/tex]
[tex]6t \equiv 0 \pmod{5}[/tex]
[tex] t \equiv 0 \pmod{5}[/tex]
[tex] t = 5u[/tex]

gir oss

[tex]x = 30u - 1[/tex]

innsatt i andre gir dette

[tex]x \equiv 5 \pmod{13}[/tex]
[tex]30u - 1 \equiv 5 \pmod{13}[/tex]
[tex]13\cdot2 u + 4u \equiv 4 \pmod{13}[/tex]
[tex] 4u \equiv 4 \pmod{13}[/tex]
[tex] u \equiv 1 \pmod{13}[/tex]
[tex] u = 13s + 1 [/tex]

Altså, får at x er lik

[tex]x = 30(13s+1) - 1 = 390s + 29[/tex]
[tex]x \equiv 390s + 29 \pmod{6\cdot5\cdot29}[/tex]
[tex]x \equiv 390s + 29 \pmod{390}[/tex]
[tex]x \equiv s + 29 \pmod{390}}[/tex]

Ja, nei, kanskje ? =)

[Vektormannen]

Fortegnsfeil igjen, [tex]30u -1 \equiv 5[/tex] gir at [tex]30u \equiv 6[/tex], ikke 4. (Nesten nederst.) Ellers ser det bra ut såvidt jeg kan se

[Nebuchadnezzar]

**** for noen feil jeg gjør da ^^

[tex]4u \equiv 6 \pmod{13}[/tex]
[tex]2u \equiv 3 \pmod{13}[/tex]
[tex]2u \equiv 16 \pmod{13}[/tex]
[tex] u \equiv 8 \pmod{13}[/tex]

Som gir

[tex]x = 30(8+13s) = 390s + 239[/tex]
[tex]x \equiv 390s + 239 \pmod{390}[/tex]
[tex]x \equiv 239 \pmod{390}[/tex]

Som eneste løsning

[Vektormannen]

Nå stemmer det ja, det ser man også ved innsetting. Jeg vet ikke om det er nødvendig å nevnte det (man ser jo strengt tatt at det bare er én løsning), men hvis man nevner at det kinesiske restteoremet garanterer at den du fant er den eneste løsningen så kan du ikke få eventuell trekk for det.