Likningssystem, modulær aritmetikk..

[mariush]

Hei.
Jeg har en oppgave:

En gruppe består av x antall elever. Dersom gruppen deles i 4, blir resten 3. Deles gruppen i 5, blir resten 4. Hvor mange elever består gruppen av? (0<x<30)

Med andre ord
x [symbol:identisk] 3 mod 4
x [symbol:identisk] 4 mod 5


I dette tilfellet er det jo lett å se at det må være 19.
Men går det ann å generalesere?

Hva gjør jeg med likninger på formen

x [symbol:identisk] r1 mod m1
x [symbol:identisk] r2 mod m2
...

? Finnes det en generell likning for slike likninger? I og med at de anntakelig får flere løsninger, må svaret oppgis som x = a +bt, hvor t er et heltall?

[mrcreosote]

Nå var du heldig, en aktiv forumdeltaker har faktisk dratt på studietur utelukkende for å lære seg mer om dette. Han kan sikkert forklare godt seinere. Ta en titt på http://en.wikipedia.org/wiki/Chinese_remainder_theorem så lenge.

[mariush]

Nå var du heldig, en aktiv forumdeltaker har faktisk dratt på studietur utelukkende for å lære seg mer om dette. Han kan sikkert forklare godt seinere. Ta en titt på http://en.wikipedia.org/wiki/Chinese_remainder_theorem så lenge.

Vakkert, takk skal du ha
Hvem er forumdeltakeren på studietur?

[Janhaa]

Nå var du heldig, en aktiv forumdeltaker har faktisk dratt på studietur utelukkende for å lære seg mer om dette. Han kan sikkert forklare godt seinere. Ta en titt på http://en.wikipedia.org/wiki/Chinese_remainder_theorem så lenge.

Vakkert, takk skal du ha
Hvem er forumdeltakeren på studietur?

daofeishi

[mariush]

Nå var du heldig, en aktiv forumdeltaker har faktisk dratt på studietur utelukkende for å lære seg mer om dette. Han kan sikkert forklare godt seinere. Ta en titt på http://en.wikipedia.org/wiki/Chinese_remainder_theorem så lenge.

Vakkert, takk skal du ha
Hvem er forumdeltakeren på studietur?

daofeishi

Ok

[FredrikM]

Spørsmål fra Abel-konkurransen? Jo, husker det. Ja, vil gjerne vite dette jeg også.

[daofeishi]

Jeg skal ihvertfall si jeg har studert det kinesiske restplassteoremet rimelig nøye den siste tida: Sengene i de siste vognene på kinesiske tog er harde.

Ellers er det kinesiske restklasseteoremet et must å ha i verktøykassa for modulær aritmetikk.

Anta at du har et sett med kongruenser der alle m er parvis relativt primiske:
[tex]x_1 \equiv a_1 \pmod{m_1} \\ x_2 \equiv a_2 \pmod{m_2} \\ \dots \\ x_ n \equiv a_n \pmod{m_n}[/tex]

La [tex] M = m_1 m_2 \dots m_n[/tex], [tex]M_i = \frac{m_1 m_2 \dots m_n}{m_i}[/tex]
og [tex]b_i[/tex] løsningen til [tex]M_i b_i \equiv 1 \pmod {m_i}[/tex]

Da er løsningen til originalsystemet gitt ved
[tex]x \equiv a_1 b_1 M_1 + a_2 b_2 M_2 + \dots + a_n b_n M_n \pmod{M}[/tex]

Kan du se hvorfor? Prøv å "arbeide baklengs" og undersøke hva svaret impliserer for x modulo hver av m'ene.

Ellers er ofte en vel så grei metode å løse kongruensene suksessivt, slik som i følgende eksempel.

La systemet være
[tex]x \equiv 2 \pmod {3} \\ x \equiv 1 \pmod 5 \\ x \equiv 4 \pmod 7[/tex]

Første kongruens impliserer at [tex]x = 2 + 3k[/tex] Sett dette inn i andre kongruens.

[tex]2 + 3k \equiv 1 \pmod 5 \\ 3k \equiv 4 \pmod 5 \\ k \equiv 3 \pmod 5[/tex]
Dette gir at [tex]k = 3 + 5l[/tex], som videre gir [tex]x = 2 + 3k = 2 + 3(3 + 5l) = 11 + 15l[/tex]

Videre har vi ved innsetting av dette i siste kongruens:
[tex]11 + 15l \equiv 4 \pmod 7 \\ l \equiv 0 \pmod 7[/tex]
Som betyr at [tex]l = 7m[/tex]

Dette gir til slutt: [tex]x = 11 + 15l = 11 + 15(7m) = 11 + 105m[/tex]
Som betyr at [tex]x \equiv 11 \pmod {105}[/tex]

[mariush]

Strålende! Takker så mye!