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!
Best Answer
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.