# What mistake did i do here? Inverse modulo calculation

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

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

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