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 prímszámra teljesül bármely egész szám esetén, hogy
.

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

  • Gyakrabban a következő (és történelmileg hitelesebb) alakban is szokás kimondani: ha prímszám és egy e prímhez relatív prím egész, akkor
.

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)Szerkeszté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   maradéka p-vel osztva 1-gyel nagyobb   maradékánál, tehát megegyezik a+1 maradékával.

2. bizonyítás (geometria)Szerkesztés

Egy szabályos p-szög mindegyik csúcsába írjuk az   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.

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

Abban a formában igazoljuk az állítást, hogy   minden p-vel nem osztható a számra. Vegyük az   maradékosztályokat modulo p, tehát a teljes redukált maradékrendszert. Az   maradékosztályok különböznek a 0 maradékosztálytól (mivel p prímszám) és egymástól is, mert   esetén p nem oszthatja  -t. Ekkor viszont   (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   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.

Kapcsolódó szócikkekSzerkesztés

További információkSzerkesztés