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.
Asked
Active
Viewed 448 times
1 Answers
1
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}$$
Yiyuan Lee
- 14,435
-
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? – arif Aug 18 '15 at 15:48
-
@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$. – Yiyuan Lee Aug 18 '15 at 15:55
-
Hi Lee, thanks for your help, appreciate it. – arif Aug 19 '15 at 06:39