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]

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.

Forrás[szerkesztés]

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