Modulo-oppgave

[Krøvel Velle Voll]

Først post her inne!
Har leita rundt her inne og lagt merke til at det er mange kompetente matematikkere her..

Sliter en del med modulær artimetikk nå før eksamen og ser at en spesiell type oppgaver går igjen på eksamen, men jeg sliter med å forstå begrepet helt bak modulo-regning.

Typsik oppgave er denne:
7x [symbol:identisk] 3 (mod 11)
9x [symbol:identisk] 9 (mod 12)
11 [symbol:identisk] 6 (mod 13)
De tre kongruensene skal altså oppfylles samtidig!

En annen helt lik er:
2x [symbol:identisk] 3 (mod 11)
3x [symbol:identisk] 9 (mod 12)
4x [symbol:identisk] 6 (mod 13)

[Janhaa]

Se om denne linken hjelper, hvis ikke fixer daofeishi dette seinere:

http://www.matematikk.net/ressurser/mat ... hp?t=16432

[Janhaa]

Først post her inne!
Har leita rundt her inne og lagt merke til at det er mange kompetente matematikkere her..
Sliter en del med modulær artimetikk nå før eksamen og ser at en spesiell type oppgaver går igjen på eksamen, men jeg sliter med å forstå begrepet helt bak modulo-regning.
En annen helt lik er:
2x [symbol:identisk] 3 (mod 11)
3x [symbol:identisk] 9 (mod 12)
4x [symbol:identisk] 6 (mod 13)

Er løsninga på dette kongruenssystemet lik:

[tex]x\equiv 172 \pmod{1716}[/tex]

Noen som kan verifisere?

Eller er jeg på sykkeltur...

[daofeishi]

Har sneket seg inn en liten feil der, Jan - Og den har nok sneket seg inn ved reduksjon av den andre kongruensen i systemet.

Systemet
[tex]2x \equiv 3 \pmod{11} \\ 3x \equiv 9 \pmod{12} \\ 4x \equiv 6 \pmod{13}[/tex]

Reduseres til systemet
[tex]x \equiv 7 \pmod{11} \\ x \equiv 3 \pmod{4} \\ x \equiv 8 \pmod{13}[/tex]

Husk at dersom [tex]ax \equiv ab \pmod m[/tex]
så er
[tex]x \equiv b \pmod{\frac{m}{\gcd(a, m)}}[/tex]

Fra det kinesiske restklasseteoremet følger det at:

[tex]x \equiv 7(52 \cdot 7) + 3(143\cdot 3) + 8(44 \cdot 8) \equiv 359 \pmod{572}[/tex]

Altså: [tex]x \equiv 359 \pmod{572}[/tex]



Ellers ville det være enklere å hjelpe trådstarter hvis det ble lagt fram litt mer konkret hva slags problemer han/hun har med modulær aritmetikk.

[Krøvel Velle Voll]

Et problem er hvordan du fks reduserte kongruensene i systemet. Har ei pensumbok (David M. Burton: "Elementary Number Theory 6. utg) som omhandler tallteori, men den er på engelsk og sliter mye med å oversett allerede vanskelig stoff fra engelsk til norsk. Har kontroll på diofantiske ligninger som er noe av det samme. Hvordan er deres måtes å angripe et slikt system på?

Takker for raske svar!

[Janhaa]

Har sneket seg inn en liten feil der, Jan - Og den har nok sneket seg inn ved reduksjon av den andre kongruensen i systemet.

Diplomatisk sagt av deg, du har riktig.

Ellers ville det være enklere å hjelpe trådstarter hvis det ble lagt fram litt mer konkret hva slags problemer han/hun har med modulær aritmetikk.

Enig, men jeg ble revet med og prøvde å løse dette sjøl.

[Janhaa]

Et problem er hvordan du fks reduserte kongruensene i systemet. Har ei pensumbok (David M. Burton: "Elementary Number Theory 6. utg) som omhandler tallteori, men den er på engelsk og sliter mye med å oversett allerede vanskelig stoff fra engelsk til norsk. Har kontroll på diofantiske ligninger som er noe av det samme. Hvordan er deres måtes å angripe et slikt system på?
Takker for raske svar!

Den første kongruens:
[tex]2x\equiv 3 \pmod{11}[/tex]
skrives:
(2x = 3 + 11 = 14)
[tex]2x\equiv 14 \pmod{11}[/tex]
[tex]x\equiv 7 \pmod {11}[/tex]


den andre kongruens:
[tex]3x\equiv 9 \pmod{12}[/tex]
(del på 3 i kongruenslikninga)
[tex]x\equiv 3 \pmod{4}[/tex]

den tredje kongruens:
[tex]4x\equiv 6 \pmod{13}[/tex]
(4x = 6 + 13*2 = 32)
[tex]4x\equiv 32 \pmod{13}[/tex]
[tex]x\equiv 8 \pmod{13}[/tex]

[daofeishi]

Her prøver jeg å gå gjennom strategiene jeg vanligvis bruker:
--------------------------------------------------------------

La oss si du har en kongruens:

[tex]ax \equiv b \pmod m[/tex]

Det første du bør tenke er: "Er kongruensen løselig"?
Siden du har kontroll på diofantiske likninger, kan det kanskje hjelpe deg å tenke at kongruensen over tilsvarer
[tex]ax = b + my \\ ax - my = b[/tex]
Som du vet bare har løsningen dersom [tex]\gcd(a, m) | b[/tex]

Deretter, sjekk om du kan fjerne noen felles faktorer. Dersom a og b har en faktor c til felles, reduser kongruensen ved:
[tex]\frac{a}{c}x \equiv \frac{b}{c} \pmod{\frac{m}{\gcd(c,m)}}[/tex] Er du heldig nå, er kongruensen redusert så mye som den kan reduseres. (Og du trenger i grunnen ikke være veldig heldig. Hvis du får [tex]a | (b + km)[/tex], ser du kanskje hvordan hele problemet er løst?)

Hvis ikke: Husk at en kongruens [tex]ax \equiv b \pmod m[/tex] har [tex]\gcd(a, m)[/tex] inkongruente løsninger [tex]\pmod{m}[/tex]
Så la oss si du fremdeles har et system på formen [tex]ax\equiv b \pmod m[/tex]. Dersom du finner én løsning [tex]x \equiv x_0 \pmod m[/tex], vil alle løsningene være gitt ved:
[tex]x \equiv x_0 + k\left( \frac{m}{\gcd(a,m)} \right) \pmod m[/tex] for heltallige k.

Så var det å finne denne ene løsninga [tex]x_0[/tex] da. Her er noen strategier:
- Prøv og feil - sett inn noen verdier av x til kongruensen stemmer. Dette går kjapt ved små moduluser.
- Gitt [tex]ax \equiv b \pmod m[/tex], se om du kan få a til å være faktor av [tex]c = b + km[/tex] for en heltallig k. Da er [tex]ax \equiv c \pmod m \qquad \Rightarrow \qquad x \equiv \frac c a \pmod{\frac{m}{\gcd(a, m)}}[/tex]
- For primtallige moduluser, bruk fermats lille teorem til å finne a's invers. Multipliser med denne inversen på begge sider.
- For ikke-primtallige moduluser kan du bruke Eulers totientfunksjon for å finne en invers. Bare pass på at gcd(a, m) = 1.

Dette burde få deg i mål.


Tenk så over hvert steg notert ned over. Prøv å bevise resultatene for deg selv, og se hvordan det gir mening. Ikke prøv å lære stegene slavisk. Etter selvransakelse virker det som om det er dette som er min standardstrategi , men kanskje du finner et annet system som passer for deg.

[Krøvel Velle Voll]

Dette var over alt forventing. Nå har jeg vertfall et mye bedre utgangspunkt for å løse disse systemene! 1000^1000 takk:)