Euler–Fermat-tétel

számelméleti állítás

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

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

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

 

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

Legyen   redukált maradékrendszer modulo  . Az   feltétel miatt az   maradékosztályok is redukált maradékrendszert alkotnak modulo  . Ekkor minden  -hez létezik egyetlen olyan  , amelyre  . Jelöljük ezt az  -t  -vel. Ekkor:

 
 
 
 

A kongruenciákat összeszorozva kapjuk:

 ,

ahol   számok az   számok egy permutációját alkotják. Ezért a kongruenciát felírhatjuk így:

 .

Mivel  , ezért a kongruencia mindkét oldalát leoszthatjuk az összes  -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

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

 

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

További információk szerkesztés

Források szerkesztés

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