Megjegyzés

Ez a tétel magától Fermat-tól származik 1636-ból. A bizonyításban felhasználtuk, hogy a kis Fermat-tétel az Euler-Fermat tétel egy speciális esete, amikoris a modulus egy $p$ prímszám, és így a $\varphi(p)$ kitevő $p-1$-gyel egyezik meg. Megemlítjük azonban, hogy az Euler-Fermat tételt Leonhard Euler mintegy 100 évvel a kis Fermat-tétel felfedezése után publikálta, méghozzá éppen annak tetszőleges – tehát nem csak prím – kitevőkre történő általánosításaként. A kis Fermat-tétel közvetlenül – tehát az Euler-Fermat tétel felhasználása nélkül – is viszonylag könnyen bizonyítható.

Vigyázat! Attól még, hogy valamely $a$ és $n$ egész számokra teljesülnek a tételben szereplő kongruenciák, még nem biztos, hogy $n$ prímszám. Ez azonban elsőre nem látszik. Például $a=2$ esetén a $2^n\equiv 2\pmod n$ kongruenciák látszólag csak azokban az esetekben teljesülnek, amikor az $n$ kitevő prím. Az első ellenpéldára csak az $n=341$ kitevőnél bukkanunk rá. Ekkor teljesül ugyan a $2^{341}\equiv 2\pmod{341}$ kongruencia, a $341$ azonban nem prím, hiszen $341=11\cdot 31$. A következő ellenpélda $n=561=3\cdot 11\cdot 17$-nél következik. Néhány továbbit találunk ebben a listában.

Ráadásul az $n=561$ ellenpélda különleges abból a szempontból, hogy esetében nemcsak az $a=2$, hanem tetszőleges $a$ alap esetén is teljesül az $a^n\equiv a\pmod n$ kongruencia, ennek ellenére $n$ mégsem prím. Másként fogalmazva ez tehát azt jelenti, hogy a tétel megfordítása nem igaz!

♣