$$24x \equiv 17 \pmod{217}$$
I got this excercise from some book, the question is - solve the congruence, using fast exponentiation algorithm to find an inverse...Hmm, do you see some inverse here to solve, or is there just a mistake in the book?
Asked
Active
Viewed 263 times
2
1 Answers
2
We show how to find the inverse of $24$ modulo $217$ by exponentiation. Note that since $217=7\cdot 31$, we have $\varphi(217)=180$. By Euler's Theorem, $24^{180}\equiv 1\pmod{217}$.
It follows that $24^{179}$ is the modular inverse of $24$. Now use fast modular exponentiation to compute $24^{179}$ modulo $217$.
Remark: Suppose that $a$ and $m$ are relatively prime. Then $a^{\varphi(m)-1}$ is the inverse of $a$ modulo $m$.
This is a lousy way of computing the modular inverse if $m$ is not large. And because there is no truly fast factorization algorithm known, it is not good for large $m$ either. However, if $m$ is known to be prime, finding $a^{m-2}\pmod{m}$ by fast exponentiation can be roughly competitive in efficiency with the Extended Euclidean Algorithm.
André Nicolas
- 507,029
\pmod{217}(parenthesized mod) to get $\pmod{217}$. Cheers – Caleb Stanford Aug 28 '13 at 19:50