Euler–Fermat-tétel

Az Euler–Fermat-tétel a számelmélet egyik nagyon fontos állítása.

A tétel állítása

Ha a és m egymáshoz relatív prímek (azaz legnagyobb közös osztójuk 1), akkor

$a^{\phi (m)}\equiv 1(\mathrm{mod}m)$

ahol φ(m) az Euler-féle φ-függvény, a pedig egy tetszőleges egész szám.

A tétel a kis Fermat-tétel általánosítása, hiszen ha p prímszám, akkor φ(p) = p – 1. A bizonyítást Leonhard Euler közölte 1736-ban.

Bizonyítása

Legyen $r_1,r_2,\dots ,r_{\phi (m)}$ redukált maradékrendszer modulo $m$. Az $(a,m)=1$ feltétel miatt az $a{r}_1,a{r}_2,\dots ,a{r}_{\phi (m)}$ maradékosztályok is redukált maradékrendszert alkotnak modulo $m$. Ekkor minden $1\le i\le \phi (m)$-hez létezik egyetlen olyan $1\le j\le \phi (m)$, amelyre $a{r}_i\equiv r_j(\mathrm{mod}m)$. Jelöljük ezt az $r_j$-t $s_i$-vel. Ekkor:

$a{r}_1\equiv s_1(\mathrm{mod}m)$

$a{r}_2\equiv s_2(\mathrm{mod}m)$

$⋮$

$a{r}_{\phi (m)}\equiv s_{\phi (m)}(\mathrm{mod}m)$

A kongruenciákat összeszorozva kapjuk:

$a^{\phi (m)}{r}_1{r}_2\dots r_{\phi (m)}\equiv s_1{s}_2\dots s_{\phi (m)}(\mathrm{mod}m)$,

ahol $r_1,r_2,\dots ,r_{\phi (m)}$ számok az $s_1,s_2,\dots ,s_{\phi (m)}$ számok egy permutációját alkotják. Ezért a kongruenciát felírhatjuk így:

$a^{\phi (m)}{r}_1{r}_2\dots r_{\phi (m)}\equiv r_1{r}_2\dots r_{\phi (m)}(\mathrm{mod}m)$.

Mivel $(r_i,m)=1$, ezért a kongruencia mindkét oldalát leoszthatjuk az összes $r_i$-vel, és akkor megkapjuk az eredeti állítást.

Megjegyzés: A tétel megfordítása is igaz.

Csoportelméleti vonatkozás

A tétel speciális esete a csoportelméleti Lagrange-tételnek. Tekintsük a modulo m vett redukált maradékrendszer G := Z^×_m multiplikatív csoportját. Ekkor G elemszáma |G| = φ(m). A Lagrange-tétel szerint egy véges G csoport tetszőleges g elemére

$g^{|G|}=e$

ahol e a G = Z^×_m csoport egységeleme.

További információk

• Alice és Bob - 20. rész: Alice, Bob, Euler és Fermat
• Alice és Bob - 22. rész: Alice, Bob és a kínaiak

Források

• Freud─Gyarmati: Számelmélet, Nemzeti Tankönyvkiadó, 2000