2
$\begingroup$

I'm in a cryptography and struggling with understanding how the Euclidean Algorithm necessarily works for finding multiplicative inverses. We haven't actually covered the algorithm yet, just a way to brute force finding the inverses but I like working with an algorithm instead of just guess and checking so I learned it myself. In the equation 1/5 mod 13 I understand that this is equivalent to 5x = 1 mod 13 however when going through the algorithm I get the answer to be -5 instead of 8 which it is supposed to be. Can anyone shed some light on where I'm going wrong? Here's my work.

(a) 1/5 mod 13

1/5 mod 13 ≡ 5-1 mod 13 ≡ 5x = 1 (mod 13)

13 = 2(5) + 3

5 = 1(3) + 2

3 = 1(2) + 1

GCD of 13 and 5 is 1.

1 = 3 – 2(1)

= 3 – (5 – 3(1)) = 3 - 5 + 3 = 2(3) - 5

= 2(13 - 2(5)) - 5

= 2(13) – 4(5) – 5

= 2(13) -5(5)

-> mod 13 on both sides

1 mod 13 = 0 – 5(5) mod 13

1 = -5(5) mod 13

x = -5

$\endgroup$
  • $\begingroup$ Welcome to MathSE. Please read this tutorial on how to typeset mathematics on this site. $\endgroup$ – N. F. Taussig Sep 19 '18 at 7:48
3
$\begingroup$

There is no mistake. $-5$ and $8$ are just equal mod $13$. They are the same number.

$\endgroup$
1
$\begingroup$

Remember $a\equiv b \pmod n$ if $a-b$ or $b-a$ is a multiple of $n$. You have $-5\equiv 8 \pmod {13}$ because $8-(-5) = {13}$ is a multiple of $13$.

$\endgroup$
0
$\begingroup$

You are right indeed by Euclidean algorithm we have

  • $13=5\cdot 2+\color{red}3$
  • $5=\color{red}3\cdot 1+\color{red}2$
  • $3=\color{red}2\cdot 1+1$

and therefore starting from the last one

$$1=3-2=3-(5-3)=2\cdot 13-2\cdot 5\cdot 2-5 \implies 2\cdot 13-5\cdot 5=1 $$$$\implies -5\cdot 5=1-2\cdot 13$$

and then

$$5x\equiv 1 \pmod {13} \implies x\equiv -5 \equiv 8 \pmod {13}$$

$\endgroup$

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.