3
$\begingroup$

I have to find the modular inverse of a sequence of numbers. When I do the inverse of $5\pmod {37}$, I get $-7$. $37 = 7(5)+2$ $5 = 2(2)+1\text{, then}$ $2 = 1(37)-7(5).$

so the inverse is $-7.$

But $-7\times 5 \pmod{37}$ is $2$. Shouldn't it be $1$?

I need to use this value for two later problems so it's messing it all up.

1 Answers 1

1

Since $5$ is coprime to $37,$ we know by Bezout's identity that $5$ is invertible mod $37$. To compute the inverse one could employ the Extended Euclidean Algorithm (which can be implemented very conveniently by hand, see here). But that algorithm is a bit overkill for such small numbers. Instead, it's simpler to employ Gauss's Algorithm and some twiddling as follows

$\rm mod\ 37\!:\,\ \frac{1}5 \equiv \frac{7}{35}\equiv \frac{-30}{-2}\equiv 15$

  • 0
    Please try the [convenient version of EEA](http://math.stackexchange.com/a/85841/242) that I linked to. It is generally easier to apply and almost always *much* less prone to errors. The correct back-substitution above is $\rm 1 = 5 - 2(\color{#C00}2) = 5 - 2(\color{#C00}{37-7(5)}) = 5-2(-7)5 - 2\cdot 37 = (1\!+2\cdot 7)\cdot 5-2\cdot 37$ Therefore $\rm\: 1 = 15\cdot 5 - 2\cdot 37\: \Rightarrow\ 1\equiv 15\cdot 5\ \, (mod\ 37)\ \ $2012-11-09