# Use Euler's theorem to find the inverse of 17 modulo 31 in the range {1,…,30}.

This is a question from the MIT opencourseware Mathematics for Computer Science, problem set 3:

Use Euler's theorem to find the inverse of $17$ modulo $31$ in the range $\{1,...,30\}$.

I don't seem to be able to actually use Euler's theorem here. Since both $17$ and $31$ are primes the $\gcd$ is $1$, so $K^{\varphi(n)-1} = 17^{29}$, which works here for an inverse, but how does that help me find an inverse in the $1,...,30$ range?

• It's not at all clear what the point of this exercise is. Perhaps they expect you to compute $\,17^{29}\,$ via exponentiation by repeated squaring and then notice right at the start that $\,17^2\equiv -1\,$ so there is a shortcut. But if you notice that then there is no need to use Euler's Theorem since that implies $\,17^{-1}\equiv -17\equiv 12.\,$ So it seems like a poorly designed exercise. Perhaps some context would help to understand the point of the exercise. – Bill Dubuque May 31 '15 at 22:18
• The first exercise of the problem is this: Use the Pulverizer to find integers s and t such that 135s + 59t = gcd(135,59). It is a problem set for a lecture that covers among other things Euler's theorem. I think it is just for the sake of making the student use Euler's theorem rather than the extended Euclidean algorithm. – aristotle85 May 31 '15 at 22:24
• What results are discussed immediately before this? – Bill Dubuque May 31 '15 at 22:25

The notes from Recitation 5 for this course describes using repeated squaring to reduce results given by Euler's Theorem. This is how I solved this problem:

$17^2$ = 289 ≡ 10 (mod 31)
$17^3$ = 4913 ≡ 15 (mod 31)
$17^6$ = $(17^3)^2$ ≡ $15^2$ = 225 ≡ 8 (mod 31)
$17^{12}$ = $(17^6)^2$ ≡ $8^2$ = 64 ≡ 2 (mod 31)

Then,

$17^{29}$ = $(17^{12})^2$ * $17^3$ * $17^2$ ≡ $(2)^2$ * 15 * 10 = 600 ≡ 11 (mod 31)

Thus,

17*11 ≡ 1 (mod 31)

So, the inverse of 17 modulo 31 in the range {1,...,30} is 11.

• If you're working things out by hand, it can save effort in problems like this if you are more aggressive in writing things as congruences rather than showing equality. For example, $17^3 \equiv 17\cdot17^2 \equiv 17\cdot10 \equiv 170 \equiv 15 \pmod{31}.$ and $2^2\cdot 15\cdot10\equiv 2\cdot(-1)\cdot10 \equiv -20\equiv 11 \pmod{31}.$ – David K Dec 31 '16 at 21:46

Rather ad hoc, I note that $17 \times 2 = 34 \equiv 3$, which is a lot easier to deal with. Then $3 \times 21 = 63 \equiv 1$, so I look at $2 \times 21 = 42 \equiv 11$.

Sure enough, $17 \times 11 = 187 \equiv 1$.

I completed this question using the following steps:

*Note: * Don't complete the computations on the right, the factorization is the part you are looking for!

$17x\equiv 1 \pmod{31}$

Step 1: $31 = 1 * 17 + 14 ... 14 = 31 - 1 * 17$

Step 2: $17 = 1 * 14 + 3 ... 3 = 17 - 1 * 14$

Step 3: $... ... 3 = 1 * 17 - 1 * [31 - 1 * 17]$

Step 4: $... ... 3 = -1 * 31 + 2 * 17$

Step 5: $14 = 4 * 3 + 2 ... 2 = 1 * 14 - 4 * 3$

Step 6: $... ... 2 = 1 * [31 - 1 * 17] - 4 * [-1 * 31 + 2 * 17]$

Step 7: $... ... 2 = 1*31 -1*17 + 4*31 - 8*17$

Step 8: $... ... 2 = 5*31 -9*17$

Step 9: $3 = 1 * 2 + 1 ... 1 = 1 * 3 - 1 * 2$

Step 10: $... ... 1 = 1 * [-1 * 31 + 2 * 17] - 1 * [ 5 * 31 - 9 * 17]$

Step 11: $... ... 1 = -1*31 + 2*17 -5*31 + 9*17$

Step 12: $... ... 1 = -6*31 + 11*17$

Finally,
$11\cdot17 \equiv 1 \pmod{31}$

So the inverse of $17 \!\mod {31}$ is $11$

• Please, use MatJax next time you write formulas... – Ottavio Bartenor Dec 21 '15 at 20:22
• @OttavioBartenor thank you for the edit! Sorry, I'm new to this and I hadn't reviewed the MatJax syntax yet. It looks a lot better now, thanks again. – Thomas Tiveron Dec 21 '15 at 20:41
• No problem, you're welcome! – Ottavio Bartenor Dec 21 '15 at 20:54