Finding multiplicative inverse Euler's theroem

Question

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.

Answer 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}$$