Kongruensligninger

[Yarril]

Jeg studerer for øyeblikket emnet diskret matematikk, og opplever store problemer med kongruensligninger av ymse slag. Både boka og nettet forøvrig har altfor simple eksempler på feltet, mens oppgavene på semesterprøvene er av den annen verden. Kunne noen forklare meg hvordan man går frem for å løse oppgaven under?

[Vektormannen]

Først kan du forenkle hver kongruens kraftig. Vi har at 14169 er kongruent med 2, som da gir at [tex]14169^{300} \equiv 2^{300} \equiv (2^5)^{60} \equiv 32^{60} \equiv 1^{60} \equiv 1[/tex]. Altså er den første kongruensen helt ekvivalent med [tex]1 + 7x \equiv 14[/tex], og det er enkelt å teste ut om x = -7 oppfyller den. Gå frem på samme måte for å se på de andre alternativene.

[Yarril]

Hvordan ser man så enkelt at 14169 er kongruent med 2? Hvorfor er 32^60 kongruent med 1^60? Jeg tror det er noe virkelig grunnleggende jeg har gått glipp av når det kommer til kongruens.

[Janhaa]

Hvordan ser man så enkelt at 14169 er kongruent med 2?

fordi

[tex]457*31+2=14169[/tex]
dvs
[tex]14169 \equiv 2 \text (mod 31)[/tex]

osv...

[Yarril]

Så for å ta for oss alternativ tre:
14167 = 31 * 487 + 0, derfor er [tex]14167^{300} \equiv 0[/tex]. Setter vi inn x = -7 i ligningen får vi -49 = 13(mod 31), og ettersom -49(mod 31) = 13 er alternativet riktig?

[Janhaa]

ja, ser ut som om både alt 1 og alt 3 er korrekte, hvis jeg har regna riktig i farta:

[tex]7x\equiv13\pmod{31}[/tex]

og der står jo hvilke i oppgava...

[Yarril]

Takk for all hjelp med oppgaven! Dessverre er det flere oppgavevarianter som stadig forvirrer meg. Ta denne for eksempel:

Jeg antar jeg må bruke en lignende teknikk som den fra forrige oppgave for å forenkle 123^1002, men jeg sliter med å få noe fornuftig ut av det.
123 = 101 * 1 + 22
101 = 22 * 4 + 13
101 = 13 * 7 + 10
101 = 10 * 10 + 1
I så fall skulle man tro at [tex]1 \equiv x\pmod{101}[/tex] var riktig, men jeg får ikke dette til å stemme med at x = -21 slik fasiten sier.

[Vektormannen]

Jeg ser ikke helt hva du har gjort. Det ser ut som du har prøvd på en eller annen form for Euklids algoritme? Det var ikke det jeg gjorde i forrige oppgave.

Her ville jeg først sett at 123 er kongruent med 22 som du sier. Så ser vi på [tex]22^2[/tex]. Det er kongruent med -21. Da har vi: [tex]123^{1002} \equiv (22^2)^{501} \equiv (-21)^{501} \equiv -21[/tex]. Er du enig i det?

[Yarril]

Jeg har problemer med å se den generelle fremgangsmåten i dette. Er det meningen at man skal omforme uttrykket spesielt for hvert enkelt svaralternativ for å se om det stemmer? Ikke minst, hvis man kan si at [tex](-21)^{501} \equiv -21[/tex], hvorfor kan man ikke da si at [tex]123^{1002} \equiv 123[/tex]?

[Vektormannen]

Der hoppet jeg nok over noen steg ja, beklager!

Hvis vi ser på [tex](-21)^{501} \equiv -21 \cdot 21^{500}[/tex], så gir Fermats lille teorem oss at [tex]21^{500} = (21^5)^{100} \equiv 1[/tex], og da er altså [tex](-21)^{501} \equiv -21 \cdot 1 = -21[/tex].

[Yarril]

I denne forenklingsprosessen endte man jo ganske tilfeldig opp med -21, men hva med de andre svaralternativene? Det er ingenting som tilsier at de ikke også stemmer. Hvordan kunne jeg eventuelt ha sjekket dem?

[Vektormannen]

Nå har vi funnet ut at x må være kongruent med -21. Da er det bare å sjekke om de andre tallene er kongruente med -21. Da finner vi at 15130 er kongruent med -20, og 15128 og 123 er kongruente med -22. Altså passer ingen av de tre inn.

[Yarril]

[tex](22^2)^{501} \equiv (-21)^{501}[/tex]

I dette trinnet, sier du at [tex]22^2 = 484 = 101 * 4 + 80 [/tex], og siden [tex]80 = 101 - 21[/tex] er -21 kongruent med 484?

[Vektormannen]

Ja, eller du kan si direkte at [tex]484 = -21 + 5 \cdot 101[/tex]. Så lenge det er en differans lik et multippel av 101 mellom tallene må de være kongruente (modulo 101).

[Yarril]

[tex]21^{500} = (21^5)^{100}[/tex]

Hvorfor faller valget på akkurat [tex](21^5)^{100}[/tex], og ikke for eksempel [tex](21^2)^{250}[/tex]? [tex]21^5[/tex] virker ikke som et spesielt praktisk eller naturlig valg. Jeg forstår rett og slett ikke hva det jobbes mot, bare at du snur om på tallene og at de på magisk vis går opp etterhvert.