Formula for the modular inverse

Question

We all know the formula for the modular inverse: $a\bar{a} \equiv 1$ (mod m), but sometimes you see the formula $\bar{a}\equiv a^{\phi(m)-1}$ (mod m).

How do you become $\bar{a}\equiv a^{\phi(m)-1}$ (mod m) from $a\bar{a} \equiv 1$ (mod m)?

Answer 1

Eulers theorem states that if $\gcd(a,m) = 1$ then $a^{\phi(m)} \equiv 1 \pmod{m}$

Knowing that then

$a \cdot a^{\phi(m) -1} \equiv a^{\phi(m)} \equiv 1 \pmod{m}$

So as you can see if we multiply $a$ by $a^{\phi(m) -1}$ we get 1, and the definition of modular inverse tells us the thing we multiplied $a$ by to get 1, is the modular inverse of $a$ and in this case that thing is $a^{\phi(m) -1}$.

Therefore $\overline{a} \equiv a^{\phi(m) -1} \pmod{m}$

Answer 2

Multiply both sides of $$\bar{a}\equiv a^{\phi(m)-1} mod(m)$$ by $ a $ and you get $$a\bar{a}\equiv a^{\phi(m)} mod(m)$$ that is $$a^{\phi(m)}=1 mod(m).$$

Answer 3

Since $$a\bar{a} \equiv 1 \pmod m$$ we have

$$\bar{a}\equiv a^{-1} \pmod m$$

But we know that if $a$ and $m$ are relatively prime (Euler theorem) then $$ a^{\phi(m)}\equiv 1 \pmod m$$ so

$$\bar{a}\equiv 1\cdot a^{-1} \equiv a^{\phi(m)-1}\pmod m$$