Malá Fermatova věta

MFV - Redukce exponentu pro prvočíslo
EV - Redukce exponentu pro ostatní

#veta Malá Fermatova věta

Buď prvočíslo a takové přirozené číslo, které není násobkem (tedy ).
Potom platí:

#dukaz Důkaz:

  • Uvažujme čísla
    • Jejich počet je
    • Jsou to nenulové zbytky
    • Žádné není kongruentní
    • Ani mezi sebou nejsou kongruentní
  • Každé z čísel vynásobíme , dostaneme tedy
    • Jejich počet je
    • Žádné není kongruentní - lze dokázat sporem:
      • Vezmeme číslo tvaru a zjišťujeme, jestli je , dostaneme spor
    • Ani mezi sebou nejsou kongruentní - lze dokázat sporem:
      • Vezmeme číslo tvaru a a zjišťujeme, jestli je , dostaneme spor
  • Z toho plyne, že a jsou vlastně v stejná čísla, jen možná v jiném pořadí
  • Tedy
  • Tedy
  • Aplikujeme krát větu o krácení v modulu (všechny čísla vyškrtám) a dostáváme

Multiplikativní inverze pomocí MFV

#tvrzeni Výpočet multiplikativní inverze pomocí MFV

Pokud je prvočíslo a , pak je multiplikativní inverzí čísla .

Tedy:

Vytvořeno: 7. 8. 2024, 13:25
Poslední aktualizace: 7. 8. 2024, 13:25