A kis Fermat-tétel bizonyításai

A kis Fermat-tétel egy számelméleti tétel, mely a maradékok (egész számok közti kongruenciák) elméletében alapvető fontosságú. A jóval nehezebb, több évszázadig megoldatlan „nagy” Fermat tételtől (külföldön Fermat utolsó tételétől – Fermat's last theorem) való megkülönböztetés miatt szokás „kis” Fermat-tételnek nevezni. Fermat egyik tételre sem adott bizonyítást, később ezt Leibniz tette meg (ld. lentebb).

• A kis Fermat-tétel tétel szerint bármely $p$ prímszámra teljesül bármely $a\in \mathbb{Z}$ egész szám esetén, hogy

$a^p\equiv a(\mathrm{mod}p)$.

Azaz ha veszünk tetszés szerint egy $a$ egész számot, megszorozzuk önmagával $p$-szer, és levonjuk belőle az a-t, akkor az eredmény $p$-vel osztható.

• Gyakrabban a következő (és történelmileg hitelesebb) alakban is szokás kimondani: ha $p$ prímszám és $a\in \mathbb{Z}$ egy e prímhez relatív prím egész, akkor

$a^{p-1}\equiv 1(\mathrm{mod}p)$.

A következőkben a tétel 3 lényegében és módszereiben különböző bizonyítása található.

1. bizonyítás (teljes indukció, binomiális tétel)

Az a természetes számra vonatkozó teljes indukcióval belátjuk, hogy az a^p hatvány p-vel osztva ugyanannyi maradékot ad, mint a, azaz

$a^p\equiv a(\mathrm{mod}p)$

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:

$(a+1{)}^p=a^p+\left(\begin{array}{c}p\\ 1\end{array}\right)a^{p-1}+\cdots +\left(\begin{array}{c}p\\ p-1\end{array}\right)a+1$

adódik.

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

$\left(\begin{array}{c}p\\ i\end{array}\right)=\frac{p!}{i!(p-i)!}$

számlálója osztható p-vel de nevezője nem. Ezért $(a+1{)}^p$ maradéka p-vel osztva 1-gyel nagyobb $a^p$ maradékánál, tehát megegyezik a+1 maradékával.

2. bizonyítás (geometria)

Egy szabályos p-szög mindegyik csúcsába írjuk az $1,\dots ,a$ számok valamelyikét. Ezt természetesen a^p-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. Ha p prím szám, akkor nem létezhet olyan konfiguráció, ami kevesebb mint p forgatással önmagába vihető. Ehhez ugyanis arra volna szükség, hogy azonos számok, egy szabályos n-szög csúcsain legyenek ($1<n<p$), ami csak úgy lehetséges, ha $p\equiv 0(\mathrm{mod}n)$, ami nem lehetséges, ha p prím. Következés képen minden csoportban pontosan p konfiguráció lesz, azaz a^p-a osztható p-vel, Quod erat demonstrandum.

3. bizonyítás (maradékosztályok)

Abban a formában igazoljuk az állítást, hogy $a^{p-1}\equiv 1(\mathrm{mod}p)$ minden p-vel nem osztható a számra. Vegyük az $1,\dots ,p-1$ maradékosztályokat modulo p, tehát a teljes redukált maradékrendszert. Az $a,2a,\dots ,(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\le i<j\le p-1$ esetén p nem oszthatja $a(j-i)$-t. Ekkor viszont $a,2a,\dots ,(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\equiv a^{p-1}A(\mathrm{mod}p)$ adódik, osztás után $a^{p-1}\equiv 1(\mathrm{mod}p)$.

Ez a bizonyítás valójában már az Euler-Fermat-tétel bizonyítását is adja.

Kapcsolódó szócikkek

• Kis Fermat-tétel
• Kongruenciák

További információk

• Alice és Bob - 22. rész: Alice, Bob és a kínaiak
• Alice és Bob - 23. rész: Alice és Bob prímszámok után nyomoz