Kis Fermat-tétel

Sablon:Humatek 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 $p$ prímszámra teljesül bármely $a \in ℤ$ egész szám esetén, hogy $a^{p} \equiv a (\mod p)$ . Azaz ha veszünk tetszés szerint egy $a$ egész számot, megszorozzuk önmagával $p$ -szer, és levonjuk belőle az a-t, akkor az eredmény $p$ -vel osztható. Gyakrabban a következő (és történelmileg hitelesebb) alakban is szokás kimondani: ha $p$ prímszám és $a \in ℤ$ egy e prímhez relatív prím egész, akkor $a^{p - 1} \equiv 1 (\mod p)$ .

Kis Fermat-tétel

Definíció

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  $p$  prímszám és  $a$  egész szám, amely nem osztható  $p$ -vel, akkor:

$a^{p - 1} \equiv 1 (\mod p) .$

Kiterjesztett Állítás

Ha $ p $ prímszám, akkor bármely $ a $ egész számra: $a^{p} \equiv a (\mod 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: $a^{p - 1} \equiv 1 (\mod p) ⟹ a^{p} = a \cdot a^{p - 1} \equiv a (\mod p) .$

Példák

Legyen $ p = 7 $ és $ a = 3 $:

$3^{7 - 1} = 3^{6} = 729 és 729 mod 7 = 1 .$

Legyen $ p = 11 $ és $ a = 2 $:

$2^{11 - 1} = 2^{10} = 1024 és 1024 mod 11 = 1 .$

Bizonyítás

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.

Számelméleti bizonyítás (maradékosztályok)

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

Tekintsük a következő sorozatot:

$a, 2 a, 3 a, \dots, (p - 1) a (\mod p) .$

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).
Vegyük az összes elem szorzatát mindkét sorozatban:

$a \cdot 2 a \cdot 3 a \cdot \dots \cdot (p - 1) a \equiv 1 \cdot 2 \cdot 3 \cdot \dots \cdot (p - 1) (\mod p) .$

A bal oldalon:

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

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

$a^{p - 1} \equiv 1 (\mod p) .$

Csoportelméleti bizonyítás

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

$a^{p - 1} \equiv 1 (\mod p) .$

Python Implementáció

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

Alkalmazások

Prímszám-tesztelés:

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

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.

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

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

$a^{- 1} \equiv a^{p - 2} (\mod p) .$

Összegzés

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.

Sablon:-ford-

Sablon:Lásd

nagy Fermat-tétel

Sablon:Hunl

Kis Fermat-tétel

Tartalomjegyzék