Fermats lille teorem

[moth]

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

[FredrikM]

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.

[moth]

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]

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]

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!