Find a multiplicative inverse of $4^{67}$ mod 19

Question

We just covered Euler's Theorem in class so I figured we were supposed to use it to find a multiplicative inverse of $4^{67}\pmod {19}$. I know that $\phi(19) = 18$, but since $(4, 18)\neq1$, I can't use it. How am I supposed to solve for the inverse instead?

Answer 1

By inspection, the multiplicative inverse of $4$ is $5$. So the multiplicative inverse of $4^{67}$ is $5^{67}$, now use Euler's or Fermat's Theorem to simplify.

Answer 2

We have $$4^2\equiv16$$ $$4^3=64\equiv7$$ $$4^4\equiv 7*4\equiv 9$$ $$4^5\equiv 9*4\equiv17$$ $$4^6\equiv 17*4\equiv11$$ $$4^7\equiv 11*4\equiv6$$ $$4^8\equiv 6*4\equiv 5$$ and $$4^9\equiv 5*4\equiv 1$$ where all equivalences are mod $19$. Thus $4^{67}\equiv 4^4\equiv 9$. This should help.

Answer 3

If $p$ is a prime, then the inverse of $a \bmod p$ is $a^{p-2}$. Also $a^n \equiv a^{n \bmod (p-1)} \bmod p$.

Therefore, the inverse of $4^{67} \bmod 19$ is $4^{67\cdot 17} \equiv 4^{67\cdot 17 \bmod 18} \equiv 4^5 = 1024 \equiv 17 \bmod 19$.

Answer 4

The nearest greater multiple of $\phi(19)=18$ over $67$ is $72$. So the multiplicative inverse is $4^{72-67}\equiv 4^5\equiv 16\cdot16\cdot 4 \equiv (-3)^2 \cdot 4 \equiv 36\equiv 17 \bmod 19$.

Answer 5

$$4^{67}=\cdots =2^{134}$$

$2^4\equiv-3,2^9=2(2^4)^2\equiv18\equiv-1\pmod{19}$

Now $134=15\cdot9-1$

$\implies(2^{134})^{-1}=(2^9)^{-15}2\equiv(-1)^{-15}2\equiv-2\equiv17$