Euler-Fermat-tétel

1. Sablon:Humatek Ha a és m egymáshoz relatív prímek (azaz legnagyobb közös osztójuk 1), akkor $a^{\phi (m)}\equiv 1(\mathrm{mod}m)$ ahol $\phi (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 $\phi (p)=p-1$.

---

Euler–Fermat-tétel

Az **Euler–Fermat-tétel** az egész számok számelméletének egyik alapvető tétele, amely általánosítja a Fermat kis tételét.

A tétel megfogalmazása

Legyen $n>1$ egy pozitív egész szám, és legyen $a$ egy olyan egész, amely relatív prím $n$-hez (azaz $\gcd (a,n)=1$). Ekkor:

$a^{\phi (n)}\equiv 1(\mathrm{mod}n),$

ahol $\phi (n)$ az $n$-hez relatív prím pozitív egész számok száma, azaz az **Euler-féle φ függvény** értéke.

Példa

Ha $n=10$, akkor $\phi (10)=4$, mert a 10-hez relatív prím számok: 1, 3, 7, 9. Ha például $a=3$, akkor:

$3^4=81\text{és}81mod10=1,$

tehát $3^4\equiv 1(\mathrm{mod}10)$.

A bizonyítás vázlata

A bizonyítás az **Egyenlő maradékosztályok elvén** és az Euler-féle φ függvény tulajdonságain alapul.

1. Az alapfeltételek

Tegyük fel, hogy $a$ és $n$ relatív prímek ($\gcd (a,n)=1$). Az $n$-hez relatív prím pozitív egész számok halmaza legyen: $R=\{r_1,r_2,\dots ,r_{\phi (n)}\},$ ahol $r_i$ elemek relatív prímek $n$-hez.

2. Az $a$-val történő szorzás

Szorozzuk meg az $R$ halmaz minden elemét $a$-val modulo $n$. Az új halmaz: $S=\{a\cdot r_{1}modn,a\cdot r_{2}modn,\dots ,a\cdot r_{\phi (n)}modn\}.$

Mivel $a$ relatív prím $n$-hez, a szorzás permutálja az $R$ elemeit. Ez azt jelenti, hogy $S$ ugyanazokat az elemeket tartalmazza, mint $R$, csak más sorrendben.

3. Szorzat modulo $n$

Az $R$ elemeinek szorzata: $r_1\cdot r_2\cdot \dots \cdot r_{\phi (n)}\equiv (a\cdot r_1)\cdot (a\cdot r_2)\cdot \dots \cdot (a\cdot r_{\phi (n)})(\mathrm{mod}n).$

Az $a$-val szorzás miatt: $r_1\cdot r_2\cdot \dots \cdot r_{\phi (n)}\equiv a^{\phi (n)}\cdot (r_1\cdot r_2\cdot \dots \cdot r_{\phi (n)})(\mathrm{mod}n).$

Mivel az $R$ elemeinek szorzata relatív prím $n$-hez, oszthatunk vele, így: $a^{\phi (n)}\equiv 1(\mathrm{mod}n).$

Megjegyzések

• Az Euler–Fermat-tétel egy speciális esete a **Fermat kis tétele**, amely azt mondja ki, hogy ha $n$ prím és $a$ nem osztható $n$-nel, akkor $a^{n-1}\equiv 1(\mathrm{mod}n)$.
• A tétel alkalmazható a modern titkosítási algoritmusokban, például az RSA algoritmusban.

• Sablon:En: Sablon:T, Sablon:T