How to find a modular multiplicative inverse when GCD is not 1 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!

$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$.
