0
$\begingroup$

been struggling this whole day with trying to figure out the multiplicative inverse of 17 modulo 31 using Eulers theorem. We know that 31 is a prime, φ(n)=30, so i end up with 17^30=(cong)1 (mod 31). But how do proceed from this to get the inverse in the range 0-30 using Eulers theorem? Would be very thankful if someone could help me out since im stuck. Thanks in advance.

$\endgroup$
1
$\begingroup$

From your working one has $$17 \cdot 17^{29} \equiv 1 \pmod {31}$$

So $17^{29}$ gives the multiplicative identity $1$ when multiplied with $17$. By the definition of inverse, $17^{29}$ is the inverse of $17$ modulo $31$. This can be further simplified, by means of repeated squaring for example, to

$$17^{29} \equiv 11 \pmod {31}$$



Repeated squaring:

Note that

$$17^{29} = 17^{16}\cdot17^8\cdot17^4\cdot17^1 \pmod {31}$$

but

$$17^1 \equiv 17 \pmod{31}$$ $$17^2 \equiv 17^2 \equiv 289 \equiv 10 \pmod{31}$$ $$17^4 \equiv 10^2 \equiv 100 \equiv 7 \pmod{31}$$ $$17^8 \equiv 7^2 \equiv 49 \equiv 18 \pmod{31}$$ $$17^{16} \equiv 18^2 \equiv 324 \equiv 14 \pmod{31}$$

so we have:

$$\begin{align}17^{29} &\equiv 17^{16}\cdot17^8\cdot17^4\cdot17^1 \pmod {31}\\ &\equiv 14\cdot18\cdot7\cdot17 \pmod {31}\\ &\equiv 29988 \pmod{31}\\ &\equiv 11 \pmod{31}\end{align}$$

$\endgroup$
  • $\begingroup$ Thanks for the answer, but havent you forgot to multiply the remainder for 17^2 (10) in step ≡14⋅18⋅7⋅17(mod31) , ? Still i dont get it how you went from 29988 to 11? $\endgroup$ – arif Aug 18 '15 at 15:48
  • $\begingroup$ @arif Hi arif, by writing $29$ as the sum of as little powers of $2$ as possible, one can omit the remainder for $17^2$. You could replace $17^4$ by $(17^2)^2$ but it would increase the amount of computation required. As for the latter part of your concern, one can subtract multiples of $31$ from $29988$ until the result is within $[0, 31)$. You could start by repeatedly subtracting $31000 = 100 \cdot 31$. $\endgroup$ – Yiyuan Lee Aug 18 '15 at 15:55
  • $\begingroup$ Hi Lee, thanks for your help, appreciate it. $\endgroup$ – arif Aug 19 '15 at 6:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.