0
$\begingroup$

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

$\endgroup$
4
  • 4
    $\begingroup$ No...by your procedure the inverse is $1$, the coefficient of $56$. $\endgroup$
    – lulu
    Sep 15, 2021 at 10:53
  • 4
    $\begingroup$ 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$. $\endgroup$
    – user700480
    Sep 15, 2021 at 10:53
  • $\begingroup$ @stinkingbishop it may be time to put that comment as an answer. $\endgroup$ Sep 15, 2021 at 12:45
  • 1
    $\begingroup$ 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. $\endgroup$
    – Peter
    Sep 15, 2021 at 14:25

1 Answer 1

1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .