Matematické Fórum

mb305 · 17. 02. 2013 11:42

Zdravím,

narazil jsem v přednáškách na pojem aditivní inverze modulo (v základech modulární aritmetiky) a bohužel jsem nepochopil, jak ji počítat. Mohl byste mě prosím někdo trknout?

Bati · 17. 02. 2013 16:32

Ahoj,
pokud to znamená hledání inverzních prvků v tělese, tak znám 2 způsoby.
1. Pomocí eulerovy věty: platí, že $\forall a\in \mathbb{Z}_p:a^{p-1}\equiv1\mod p$ , tudíž pokud dostanu číslo $a$ , tak jeho inverz je $a^{p-2}\mod p$ .
2. Většinou rychlejší způsob je použít Bézoutovu rovnost: Pokud mám číslo $a\in\mathb{Z}_p$ , pak $\text{NSD}\,(a,p)=1=u\cdot a+v\cdot p\equiv u\cdot a\mod p$ . Čili stačí nalézt číslo $u$ pomocí Euklidova algoritmu.