A kis Fermat-tétel bizonyításai
A Wikipédiából, a szabad lexikonból.
A Kis Fermat-tétel bizonyításai.
[szerkesztés] 1. bizonyítás
Az a természetes számra vonatkozó teljes indukcióval belátjuk, hogy az ap hatvány p-vel osztva ugyanannyi maradékot ad, mint a, azaz

a = 1 -re a tétel állítása nyilvánvalóan teljesül, hiszen ekkor a hatvány értéke 1.
Tegyük fel, hogy a-ra igaz az állítás. A binomiális tétel felhasználásával bebizonyítjuk, hogy ekkor (a+1)p is ugyanannyi maradékot ad p-vel osztva mint a + 1. A binomiális tétel szerint ugyanis:

adódik.
Itt a közbülső tagokban szereplő binomiális együtthatók mindegyike osztható p-vel, hiszen p prím és

számlálója osztható p-vel de nevezője nem. Ezért (a + 1)p maradéka p-vel osztva 1-gyel nagyobb ap maradékánál, tehát megegyezik a+1 maradékával.
[szerkesztés] 2. bizonyítás
Egy szabályos p-szög mindegyik csúcsába írjuk az 1,...,a számok valamelyikét. Ezt természetesen ap-féleképpen tehetjük meg. Ezek között a olyan van, amiben csupa azonos számot írtunk. A többieket csoportokba osztjuk egy csoportba téve azokat, amelyek egymásból elforgatással megkaphatók. Könnyen láthatóan minden csoportban pontosan p konfiguráció lesz, azaz ap-a osztható p-vel, Quod erat demonstrandum.
[szerkesztés] 3. bizonyítás
Abban a formában igazoljuk az állítást, hogy
mod p minden p-vel nem osztható a számra. Vegyük az 1,...,p-1 maradékosztályokat modulo p, tehát a teljes redukált maradékrendszert. Az a, 2a,...,(p-1)a maradékosztályok különböznek a 0 maradékosztálytól (mivel p prímszám) és egymástól is, mert 1≤i<j ≤ p-1 esetén p nem oszthatja a(j-i)-t. Ekkor viszont a, 2a,...,(p-1)a (valamilyen sorrendben) ismét a teljes redukált maradékrendszer, ezért szorzatuk ugyanaz a nemnulla A maradékosztály (ami -1 a Wilson-tétel miatt, de erre nincs szükségünk). Kiemelve az a tényezőket A≡ap-1 A mod p adódik, osztás után
.
Ez a bizonyítás valójában már az Euler-Fermat-tétel bizonyítását is adja.


Based on work by