Euler-Fermat-tétel

• IPA:

Euler-Fermat-tétel

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

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.

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

${\displaystyle a^{\varphi (n)}\equiv 1{\pmod {n}},}$

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

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

${\displaystyle 3^{4}=81\quad {\text{és}}\quad 81\mod 10=1,}$

tehát ${\displaystyle 3^{4}\equiv 1{\pmod {10}}}$.

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

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

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

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

Az ${\displaystyle R}$ elemeinek szorzata: ${\displaystyle r_{1}\cdot r_{2}\cdot \ldots \cdot r_{\varphi (n)}\equiv (a\cdot r_{1})\cdot (a\cdot r_{2})\cdot \ldots \cdot (a\cdot r_{\varphi (n)}){\pmod {n}}.}$

Az ${\displaystyle a}$-val szorzás miatt: ${\displaystyle r_{1}\cdot r_{2}\cdot \ldots \cdot r_{\varphi (n)}\equiv a^{\varphi (n)}\cdot (r_{1}\cdot r_{2}\cdot \ldots \cdot r_{\varphi (n)}){\pmod {n}}.}$

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

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

• angol: Fermat-Euler theorem (en), Euler's totient theorem (en)

• Euler-Fermat-tétel - Értelmező szótár (MEK)
• Euler-Fermat-tétel - Etimológiai szótár (UMIL)
• Euler-Fermat-tétel - Szótár.net (hu-hu)
• Euler-Fermat-tétel - DeepL (hu-de)
• Euler-Fermat-tétel - Яндекс (hu-ru)
• Euler-Fermat-tétel - Google (hu-en)
• Euler-Fermat-tétel - Helyesírási szótár (MTA)
• Euler-Fermat-tétel - Wikidata
• Euler-Fermat-tétel - Wikipédia (magyar)