Euler-Fermat-tétel

Magyar

Kiejtés

IPA: [ ˈɛulɛrfɛrmɒtːeːtɛl]

Főnév

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

ahol $\varphi (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 $\varphi (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\quad {\text{és}}\quad 81\mod 10=1,$

tehát $3^{4}\equiv 1{\pmod {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},\ldots ,r_{\varphi (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}\mod n,a\cdot r_{2}\mod n,\ldots ,a\cdot r_{\varphi (n)}\mod n\}.$

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 \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 $a$ -val szorzás miatt: $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 $R$ elemeinek szorzata relatív prím $n$ -hez, oszthatunk vele, így: $a^{\varphi (n)}\equiv 1{\pmod {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{\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)

További információk

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)