0

I want to find the inverse of $56 \bmod 5$ so $56x \equiv 1 \bmod 5$. With the eye we can easily see that $x=1$ but i want to follow the procedure.

So i proceed with the extended Euclidian algorithm

$56 = 11 \cdot 5 + 1$

So

$1 = -11 \cdot 5 + 1 \cdot 56$

Since we want the inverse to be in $[1,55]$

$1=(45-56) \cdot 5 + 1 \cdot 56$

So by this procedure it would be $x=45$ which is obviously not correct.

What am i doing wrong here? I thought i followed the algorithm steps accurately

Than1
  • 331
  • 4
    No...by your procedure the inverse is $1$, the coefficient of $56$. – lulu Sep 15 '21 at 10:53
  • 4
    The inverse will be the number multiplying $56$ - not the number multiplying the modulus $5$. Thus, already from $1=-11\cdot 5+\color{red}{1}\cdot 56$ you can see that the inverse is $1$. –  Sep 15 '21 at 10:53
  • @stinkingbishop it may be time to put that comment as an answer. – Oscar Lanzi Sep 15 '21 at 12:45
  • 1
    Why not first apply the modulo-operator for both sides which here gives $x\equiv 1\mod 5$. Before determining the inverse, it makes sense to work with numbers as small as possible. – Peter Sep 15 '21 at 14:25

1 Answers1

1

You simply picked the wrong coefficient. $45$ is $5^{-1}\bmod 56$ . To reduce error, it might be good reduce modulo $5$ first.

Roddy MacPhee
  • 859