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
Fermats lille teorem
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
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)).
Du trenger ikke dette. Det holder at [tex]m \equiv n \pmod p[/tex] siden du tross alt regner modulo p.så vil k være 0 i ligningen m=n+pk pågrunn av at m er mindre enn p
Cube - mathematical prethoughts | @MatematikkFakta
Med forbehold om tullete feil. (både her og ellers)
Med forbehold om tullete feil. (både her og ellers)
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
Men jeg konkluderer fra ditt innlegg at jeg ihvertfall ikke har gjort noen alvorlige feil.
Takk for svaret
For [tex]a\equiv 0\, mod(p)[/tex] gjelder ekvivalensen åpenbart. La derfor a og p være innbyrdes primiske.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.
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.