How to find a modular multiplicative inverse when GCD is not 1

Question

I am working on a problem that requires finding a multiplicative inverse of two numbers, but my algorithm is failing for a very simple reason: the GCD of the two numbers isn't 1. I figured I must've made a mistake, but after checking and rechecking the numbers I don't think I have.

So, my question is--is there any way to find a modular inverse when the numbers start out with GCD does not equal 1? Any little manipulations I can pull to make it work and then undo later? (For example, in my case the GCD=2, so I tried simply dividing the modulus and the other number by 2. It didn't work, but maybe that is the approach and I'm just trying to do it/undo it wrong at the end).

Here is my code snippet:

message = 20543;
sigX = 20679;
sigY = 11082;       
a = 7973;   
p = 31847;      
p = p-1;
int abc = (message-((a*sigX) % p));
abc = abc % p;  
if (abc<0){
    abc+=p;
}
int def = getMIM(p, abc);
System.out.println("abc  = "+abc);
System.out.println(def);
int invK = (sigY*def)%p;
System.out.println("invK = "+invK);
System.out.println("MIMtest--should equal 1... : "+(abc*def)%p);
int realK = getMIM(p, invK);
System.out.println("real k = "+realK);

Thanks in advance, guys!

Answer 1

$gcd(a,b)=1 \iff \exists r,s : ra+sb=1 \iff \exists r: ra \equiv 1 \text{ mod } b \iff a \in (\mathbb Z/b \mathbb Z)^*$ (units of $\mathbb Z/b \mathbb Z$) And as you can see in the second last step the units are the invertible elements of $\mathbb Z/b \mathbb Z$. That means if $gcd(a,b) \neq 1$ then $a$ is not invertible in $\mathbb Z/b \mathbb Z$.

Answer 2

Wikihow notes in part:

If it isn't already, put the equation in the form ax + by = c.

....

If a, b, and c have a common factor, then simplify the equation by dividing the left and right sides of the equation by that factor. If a and b have a common factor not shared by c, then stop. There are no integer solutions.

Answer 3

Say there is an inverse to $a$ mod $b$. Call it $x$. Then $ax \equiv 1 \pmod{b}$. This is the same thing as saying $ax + by = 1$ for some $y \in \mathbb{Z}$. But if $a$ and $b$ have a common factor $d$, then cleary $d$ divides $1$. This forces $d = \pm 1$, so the GCD of $a$ and $b$ must be $1$.

Therefore, inverses exist iff $a$ is coprime to $b$.

Answer 4

Multiplicative inverses only exist when the gcd is $1$. Let's see why.

Suppose our two numbers $a,b$ have gcd $d > 1$. Our goal is to find a multiplicative inverse for $a \pmod b$, which means we want to find an $x$ so that

$$ax \equiv 1 \pmod b.$$

Translating this out of mod notation means we want an $x$ so that $ax = 1 + by$, for some $y$. Rearranging this gives

$$ax - by = 1.$$

The problem is that $d$ divides both $a$ and $b$, and so $d$ divides the left hand side. This means $d$ must divide the right hand side too, but this is impossible as $d > 1$. So we do not have a multiplicative inverse.