Euler–Fermat-tétel

A Wikipédiából, a szabad enciklopédiából

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

A tétel állítása[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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_1r_2 \dots r_{\varphi(m)} \equiv s_1s_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_1r_2 \dots r_{\varphi(m)} \equiv r_1r_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[szerkesztés | forrásszöveg szerkesztése]

A tétel speciális esete a csoportelméleti Lagrange-tételnek. Tekintsük a moduló 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.

Forrás[szerkesztés | forrásszöveg szerkesztése]

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