0
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Bill Dubuque May 31 '15 at 22:18
  • $\begingroup$ 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. $\endgroup$ – aristotle85 May 31 '15 at 22:24
  • 1
    $\begingroup$ What results are discussed immediately before this? $\endgroup$ – Bill Dubuque May 31 '15 at 22:25
2
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ 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}.$ $\endgroup$ – David K Dec 31 '16 at 21:46
1
$\begingroup$

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$.

|cite|improve this answer
$\endgroup$
1
$\begingroup$

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$

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ Please, use MatJax next time you write formulas... $\endgroup$ – Ottavio Bartenor Dec 21 '15 at 20:22
  • $\begingroup$ @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. $\endgroup$ – Thomas Tiveron Dec 21 '15 at 20:41
  • $\begingroup$ No problem, you're welcome! $\endgroup$ – Ottavio Bartenor Dec 21 '15 at 20:54

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.