Fermats lille teorem

Mange finner bevis vanskelig. Her er rom for spørsmål vedrørende bevis, og for å dele dine bevis med andre. Vi tenker først og fremst videregående nivå, men det er ingen begrensninger her.

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

Svar
moth
Hilbert
Hilbert
Innlegg: 1081
Registrert: 08/03-2008 19:47

I forbindelse med en oppgave jeg holder på med skal jeg bevise Fermats lille teorem og lurte på om noen kunne se på beviset mitt at jeg har forstått det riktig.

Jeg skal altså bevise at [tex]a^p\equiv a\;\pmod p[/tex]

Starter først med å liste opp tallene [tex]a,\;2a,\;3a,\;...,\;(p-1)a\;\;\;\;\;\;\;[/tex] (1)

Så finner jeg kongruensen til hvert ledd i (1) modulo p. Ingen av de kan være kongruent med 0 (mod p) siden p ikke er faktor i a og alle koeffisientene til a er mindre enn p. I tillegg må alle kongruensene være distinkt siden hvis ma og na er to ledd i (1) og vi setter [tex]ma\equiv na\;\pmod p\;\to\;m\equiv n\;\pmod p[/tex] så vil k være 0 i ligningen m=n+pk pågrunn av at m er mindre enn p. Det gir m=n som ikke kan stemme. Kongruensene vil da være en permutasjon av tallene [tex]1,\;2,\;3,\;...,\;(p-1)[/tex]

Siden alle kongruensene er modulo p så kan vi gange alle sammen slik at [tex]a\cdot2a\cdot3a\cdot...\cdot(p-1)a\;\equiv \;1\cdot2\cdot3\cdot...\cdot(p-1)\; \pmod{p}[/tex]

Som kan skrives som [tex]a^{p-1}(p-1)!\;\equiv\;(p-1)!\;\pmod{p} [/tex]

Og siden [tex]sfd((p-1)!,\;p)=1[/tex] fordi alle leddene i (p-1)! er mindre enn p, kan vi forkorte den kongruensen til [tex]a^{p-1}\;\equiv\;1\;\pmod{p}[/tex]

Så ganger vi med a på begge sider og får [tex]a^p\;\equiv\;a\;\pmod{p}[/tex]

Holder dette som bevis eller har jeg gjort noen feil?
Jeg lurer og litt på hvordan jeg kan vise at ingen av tallene i (1) er kongruent med p (mod p) eller "større enn p" (mod p). Jeg føler det er ganske intuitivt, men det hadde vært greit å kunne vise det matematisk.

Håper noen kan hjelpe :D
FredrikM
Poincare
Poincare
Innlegg: 1367
Registrert: 28/08-2007 20:39
Sted: Oslo
Kontakt:

Du bruker veldig ofte uttrykket "mindre enn". Det gir ikke særlig mening når vi regner modulo. (for vanligvis er 2 < 4, men modulo 3 blir 2 ">" 4 (fordi 4=1 mod 3)).
så vil k være 0 i ligningen m=n+pk pågrunn av at m er mindre enn p
Du trenger ikke dette. Det holder at [tex]m \equiv n \pmod p[/tex] siden du tross alt regner modulo p.
Cube - mathematical prethoughts | @MatematikkFakta
Med forbehold om tullete feil. (både her og ellers)
moth
Hilbert
Hilbert
Innlegg: 1081
Registrert: 08/03-2008 19:47

Jeg vet jeg er veldig pirkete, men det er bare sånn at alt står klart for meg hva som skjer og hvorfor. At jeg bruker "mindre enn p" er jo fordi at det betyr at p ikke kan gå opp i tallet.
Men jeg konkluderer fra ditt innlegg at jeg ihvertfall ikke har gjort noen alvorlige feil.
Takk for svaret :)
Gustav
Tyrann
Tyrann
Innlegg: 4555
Registrert: 12/12-2008 12:44

moth skrev: Jeg lurer og litt på hvordan jeg kan vise at ingen av tallene i (1) er kongruent med p (mod p) eller "større enn p" (mod p). Jeg føler det er ganske intuitivt, men det hadde vært greit å kunne vise det matematisk.
For [tex]a\equiv 0\, mod(p)[/tex] gjelder ekvivalensen åpenbart. La derfor a og p være innbyrdes primiske.

Siden p er et primtall impliserer [tex]na\equiv 0 \,mod(p)[/tex] at enten er [tex]n\equiv 0[/tex] eller [tex]a\equiv 0 \,mod(p)[/tex]. Men vi vet jo at hverken a eller n er ekvivalent med 0 modulo p, så [tex]na[/tex] kan ikke være ekvivalent med 0 modulo p.
moth
Hilbert
Hilbert
Innlegg: 1081
Registrert: 08/03-2008 19:47

Ja, jeg tenkte på det litt etter jeg skrev innlegget at jeg glemte å skrive at p ikke skal være faktor i a. Og hvis kongruensen er større enn p er det jo bare å trekke fra p så no har jeg det tror jeg:) Takk!
Svar