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^{\varphi (m)}\equiv 1{\pmod {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_{\varphi (m)}$ redukált maradékrendszer modulo $m$. Az $\ (a,m)=1$ feltétel miatt az $ar_{1},ar_{2},\dots ,ar_{\varphi (m)}$ maradékosztályok is redukált maradékrendszert alkotnak modulo $m$. Ekkor minden $1\leq i\leq \varphi (m)$-hez létezik egyetlen olyan $1\leq j\leq \varphi (m)$, amelyre $ar_{i}\equiv r_{j}{\pmod {m}}$. Jelöljük ezt az $r_{j}$-t $s_{i}$-vel. Ekkor:

$ar_{1}\equiv s_{1}{\pmod {m}}$

$ar_{2}\equiv s_{2}{\pmod {m}}$

$\vdots$

$ar_{\varphi (m)}\equiv s_{\varphi (m)}{\pmod {m}}$

A kongruenciákat összeszorozva kapjuk:

$a^{\varphi (m)}r_{1}r_{2}\dots r_{\varphi (m)}\equiv s_{1}s_{2}\dots s_{\varphi (m)}{\pmod {m}}$,

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

$a^{\varphi (m)}r_{1}r_{2}\dots r_{\varphi (m)}\equiv r_{1}r_{2}\dots r_{\varphi (m)}{\pmod {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