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 legfontosabb állítása.

Tartalomjegyzék

[szerkesztés] A tétel állítása

Ha a és m egymáshoz relatív prímek, akkor

a^{\varphi(m)} \equiv 1 \pmod{m}

ahol φ(m) az Euler-féle φ-függvény.

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.

[szerkesztés] 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 rj-t si-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 ri-vel, és akkor megkapjuk az eredeti állítást.

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

[szerkesztés] Csoportelméleti vonatkozás

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.

[szerkesztés] Forrás

  • Freud─Gyarmati: Számélmélet, Nemzeti Tankönyvkiadó, 2000
A lap eredeti címe: „http://hu.wikipedia.org/wiki/Euler%E2%80%93Fermat-t%C3%A9tel”
Személyes eszközök