kis Fermat-tétel

• IPA:

kis Fermat-tétel

1. (matematika) A kis Fermat-tétel egy számelméleti tétel, mely a maradékok (egész számok közti kongruenciák) elméletében alapvető fontosságú. A kis Fermat-tétel szerint bármely ${\displaystyle p}$ prímszámra teljesül bármely ${\displaystyle a\in \mathbb {Z} }$ egész szám esetén, hogy ${\displaystyle a^{p}\equiv a{\pmod {p}}}$. Azaz ha veszünk tetszés szerint egy ${\displaystyle a}$ egész számot, megszorozzuk önmagával ${\displaystyle p}$-szer, és levonjuk belőle az a-t, akkor az eredmény ${\displaystyle p}$-vel osztható. Gyakrabban a következő (és történelmileg hitelesebb) alakban is szokás kimondani: ha ${\displaystyle p}$ prímszám és ${\displaystyle a\in \mathbb {Z} }$ egy e prímhez relatív prím egész, akkor ${\displaystyle a^{p-1}\equiv 1{\pmod {p}}}$.

A **kis Fermat-tétel** a számelmélet egy alapvető eredménye, amely a prímszámokkal és a hatványozással foglalkozik. A tétel kimondja:

Ha ${\displaystyle p}$ prímszám és ${\displaystyle a}$ egész szám, amely nem osztható ${\displaystyle p}$-vel, akkor: 

$${\displaystyle a^{p-1}\equiv 1{\pmod {p}}.}$$

Ha \( p \) prímszám, akkor bármely \( a \) egész számra: ${\displaystyle a^{p}\equiv a{\pmod {p}}.}$

Ez az állítás következik a kis Fermat-tételből: - Ha \( a \) osztható \( p \)-vel, akkor az egyenlőség triviálisan teljesül. - Ha \( a \) nem osztható \( p \)-vel, akkor: ${\displaystyle a^{p-1}\equiv 1{\pmod {p}}\implies a^{p}=a\cdot a^{p-1}\equiv a{\pmod {p}}.}$

1. Legyen \( p = 7 \) és \( a = 3 \):

${\displaystyle 3^{7-1}=3^{6}=729\quad {\text{és}}\quad 729\mod 7=1.}$

1. Legyen \( p = 11 \) és \( a = 2 \):

${\displaystyle 2^{11-1}=2^{10}=1024\quad {\text{és}}\quad 1024\mod 11=1.}$

A kis Fermat-tétel többféleképpen bizonyítható. Az alábbiakban két közismert bizonyítást mutatunk be: a számelméleti tulajdonságokon alapuló bizonyítást és a csoportelméleti bizonyítást.

Legyen \( a \) olyan egész szám, amely nem osztható \( p \)-vel (\( \gcd(a, p) = 1 \)).

1. Tekintsük a következő sorozatot:

${\displaystyle a,2a,3a,\dots ,(p-1)a\quad {\pmod {p}}.}$

1. Mivel \( a \) relatív prím \( p \)-hez, a sorozat \( \mod{p} \)-ban vett maradékai \( \{1, 2, \dots, p-1\} \)-vel ekvivalensek (azaz permutálják azokat).
2. Vegyük az összes elem szorzatát mindkét sorozatban:

${\displaystyle a\cdot 2a\cdot 3a\cdot \dots \cdot (p-1)a\equiv 1\cdot 2\cdot 3\cdot \dots \cdot (p-1){\pmod {p}}.}$

1. A bal oldalon:

${\displaystyle a^{p-1}\cdot (p-1)!\equiv (p-1)!{\pmod {p}}.}$

1. Mivel \( (p-1)! \) osztható \( p \)-vel, egyszerűsíthetünk \( (p-1)! \)-val:

${\displaystyle a^{p-1}\equiv 1{\pmod {p}}.}$

1. A nemnulla elemek \( \mod{p} \)-ban (azaz \( \{1, 2, \dots, p-1\} \)) multiplikatív csoportot alkotnak modulo \( p \).
2. Ez a csoport \( p-1 \) elemű, mivel minden elem inverzibilis \( \mod{p} \).
3. Ha \( a \) nem osztható \( p \)-vel, akkor \( a \) is eleme ennek a csoportnak.
4. A csoport minden elemének hatványai \( a^{p-1} \) alakban adják vissza az egységelemet (1):

${\displaystyle a^{p-1}\equiv 1{\pmod {p}}.}$

def fermat_theorem(a, p):
    """
    Ellenőrzi a kis Fermat-tételt: a^(p-1) ≡ 1 (mod p).

    Args:
        a: Az alap (egész szám).
        p: A prímszám.

    Returns:
        True, ha a^(p-1) ≡ 1 (mod p), különben False.
    """
    if a % p == 0:
        return False  # a nem lehet osztható p-vel
    return pow(a, p - 1, p) == 1

# Példa használat
print(fermat_theorem(3, 7))  # True
print(fermat_theorem(2, 11))  # True

1. Prímszám-tesztelés:

  - A kis Fermat-tétel alapot ad a Miller-Rabin és más hatékony prímszámtesztekhez.

1. Kriptográfia:

  - A nyilvános kulcsú titkosítások, például az RSA, erősen támaszkodnak a moduláris aritmetikára és a kis Fermat-tételre.

1. Moduláris inverz számítás:

  - Az \( a^{-1} \pmod{p} \) kiszámítható:

${\displaystyle a^{-1}\equiv a^{p-2}{\pmod {p}}.}$

A **kis Fermat-tétel** a számelmélet egyik alapvető állítása, amely a prímszámokkal és a moduláris aritmetikával foglalkozik. Bizonyítása egyszerű, de rendkívül fontos matematikai és gyakorlati alkalmazások alapjául szolgál. Felhasználása különösen jelentős a kriptográfiában és a számítógépes algoritmusok tervezésében.

• angol: Fermat's little theorem (en)
• francia: petit théorème de Fermat (fr)
• orosz: малая теорема Ферма (ru) (malaja teorema Ferma)

• nagy Fermat-tétel

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