Using Fermat's little theorem, we know that
$$k^{p-2} \cdot k \equiv 1 \pmod p.$$
To find the multiplicative inverse of $6$ modulo $17$, we need to calculate $6^{15} \pmod {17}$. It's supposed to be all congruences hold modulo $17$.
$$6^{15} \equiv 6^8 \cdot 6^4 \cdot 6^2 \cdot 6 \equiv 16\cdot4\cdot2\cdot6 \equiv 3 \pmod {17}$$
I need help to understand the solution of $6^{15} \equiv 3 \pmod {17}$.
Thanks.
Best Answer
$15 = 8+4+2+1$, hence $6^{15} = 6^8 \cdot 6^4\cdot 6^2\cdot 6^1$. Then:
$6^1 \equiv 6 \pmod{17}$
$6^2 = 36 \equiv 2 \pmod{17}$
$6^4 = (6^2)^2 \equiv 2^2 = 4 \pmod{17}$
$6^8 = (6^4)^2 \equiv 4^2 = 16 \pmod{17}$
Therefore $6^{15} \equiv 16 \cdot 4\cdot 2 \cdot 6 = 16\cdot 48 = (17-1)(51-3) \equiv 3 \pmod{17}$