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?
Kongruensligninger
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
-
- Euler
- Innlegg: 5889
- Registrert: 26/09-2007 19:35
- Sted: Trondheim
- Kontakt:
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.
Elektronikk @ NTNU | nesizer
fordiHvordan ser man så enkelt at 14169 er kongruent med 2?
[tex]457*31+2=14169[/tex]
dvs
[tex]14169 \equiv 2 \text (mod 31)[/tex]
osv...
La verken mennesker eller hendelser ta livsmotet fra deg.
Marie Curie, kjemiker og fysiker.
[tex]\large\dot \rho = -\frac{i}{\hbar}[H,\rho][/tex]
Marie Curie, kjemiker og fysiker.
[tex]\large\dot \rho = -\frac{i}{\hbar}[H,\rho][/tex]
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...
[tex]7x\equiv13\pmod{31}[/tex]
og der står jo hvilke i oppgava...
La verken mennesker eller hendelser ta livsmotet fra deg.
Marie Curie, kjemiker og fysiker.
[tex]\large\dot \rho = -\frac{i}{\hbar}[H,\rho][/tex]
Marie Curie, kjemiker og fysiker.
[tex]\large\dot \rho = -\frac{i}{\hbar}[H,\rho][/tex]
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.
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.
-
- Euler
- Innlegg: 5889
- Registrert: 26/09-2007 19:35
- Sted: Trondheim
- Kontakt:
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?
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?
Elektronikk @ NTNU | nesizer
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]?
-
- Euler
- Innlegg: 5889
- Registrert: 26/09-2007 19:35
- Sted: Trondheim
- Kontakt:
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].
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].
Elektronikk @ NTNU | nesizer
-
- Euler
- Innlegg: 5889
- Registrert: 26/09-2007 19:35
- Sted: Trondheim
- Kontakt:
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.
Elektronikk @ NTNU | nesizer
-
- Euler
- Innlegg: 5889
- Registrert: 26/09-2007 19:35
- Sted: Trondheim
- Kontakt:
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).
Elektronikk @ NTNU | nesizer
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.Vektormannen skrev:[tex]21^{500} = (21^5)^{100}[/tex]