Euler–Fermat-tétel

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

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

${\displaystyle 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.

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

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

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

${\displaystyle \vdots }$

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

A kongruenciákat összeszorozva kapjuk:

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

ahol ${\displaystyle r_{1},r_{2},\dots ,r_{\varphi (m)}}$ számok az ${\displaystyle 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:

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

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

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

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

${\displaystyle g^{|G|}=e\,}$

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

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

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