Kongruensregning

Her kan brukere av forum utfordre hverandre med morsomme oppgaver og nøtter man ønsker å dele med andre. Dette er altså ikke et sted for desperate skrik om hjelp, de kan man poste i de andre forumene, men et sted for problemløsing på tvers av trinn og fag.

Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa

Andreas_Holmstrom
Fibonacci
Fibonacci
Innlegg: 4
Registrert: 25/01-2016 00:38

Forenkle problemet er feil uttrykk. Jeg mener at hvis du først prøver å løse et annet lignende men enklere problem så kan det hende at du får idéer og aha-opplevelser som du så kan bruke når du angriper det opprinnelige problemet på nytt.

Hvor mye har du arbeidet med kongruenser tidligere? Hvis du er helt fersk så kanskje dette ikke er den beste oppgaven å begynne med ;-)

For å finne dette enklere problemet gjettet jeg bare at kongruensen [tex]a^{b^c} + c^{b^a} \equiv 0 \pmod {b^b}[/tex] alltid gjelder når a, b, c er konsekutive positive heltall. Kan hende jeg gjetter helt feil, men jeg klarte ihvertfall å bevise det når a=2, og hvis din oppgave er riktig formulert så skal det jo også gjelde for a=1980.

Derimot har jeg så langt ikke klart å bevise det for a=1980.

En generell idé som ofte hjelper når vi har både potenser og kongruenser i samme oppgave er å se på den multiplikative gruppen av invertible elementer mod m (her er m = b^b). Da kan vi ofte "oversette" den opprinnelige kongruensen til et enklere utsagn om eksponentene.

En annen idé som muligens kan hjelpe er å skrive a= b-1 og c = b+1, og prøve å utvikle de to uttrykkene som binomialuttrykk. En del av leddene du da får er åpenbart delelige med [tex]b^b[/tex], men jeg vet ikke om dette fører noen vei.

Hvis du vil har mere hjelp kanskje du kan fortelle hva du har prøvd, og også si litt om hvor mye du kan om kongruenser fra før av? Kjenner du f.eks. til teorien for primitive røtter eller ikke?
Gustav
Tyrann
Tyrann
Innlegg: 4563
Registrert: 12/12-2008 12:44

Det skal gå an å vise at $1982^{1981^{1980}}\equiv 1 \,\mod 1981^{1981}$:

Fra Eulers produktformel har vi at $\varphi(1981^{1981})=\varphi(7^{1981}283^{1981})=1981^{1981}(1-\frac{1}{7})(1-\frac{1}{283})=1981^{1981}\frac{6}{7}\cdot \frac{282}{283}=1981^{1980}\cdot 6\cdot 282$.


$a^{1981^{1980}\cdot 6\cdot 282}\equiv 1\mod 1981^{1981}$ (Eulers teorem for $a$ relativt primisk med $1981^{1981}$)

$(a^{6\cdot 282})^{1981^{1980}}\equiv 1\mod 1981^{1981}$

Kan vi finne en $a$ slik at $a^{1692}\equiv 1982\mod 1981^{1981}$?

Det går kanskje an å bruke det kinesiske restteoremet for å redusere problemet til to likninger, og deretter noen resultater om primitive røtter modulo $p^n$ for odde primtall $p$.
Andreas_Holmstrom
Fibonacci
Fibonacci
Innlegg: 4
Registrert: 25/01-2016 00:38

Kanskje kan Hensels lemma være til hjelp? Har ikke prøvd selv.
Gustav
Tyrann
Tyrann
Innlegg: 4563
Registrert: 12/12-2008 12:44

Ser nå at denne løses på samme måte som http://www.matematikk.net/matteprat/vie ... 54#p197254
Svar