# 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);


• The inverse of $a\pmod{b}$ exists only if $\gcd(a,b)=1$. How can you have $c\cdot a\equiv 1\pmod{b}$ if the LHS is a multiple of the $\gcd$ while the RHS is not? – Jack D'Aurizio Aug 17 '14 at 22:34
• I'm not quite sure I understand you. Can you please explain more specifically where the mistake is that you are pointing out? – Jo.P Aug 17 '14 at 22:41
• Use the extended-euclidean algorithm. It is an extension to the modular multiplicative inverse. – Ryan Aug 17 '14 at 22:42
• You're trying to find something which doesn't exist ($b$ doesn't have an inverse modulo $a$ when $\gcd(a,b)$ is not $1$). – Dan Rust Aug 17 '14 at 22:42

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.

• well played bro – rakeb.mazharul May 30 '16 at 16:17

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

• Er…can you explain that a little more with regular words? I got lost in the symbols... – Jo.P Aug 17 '14 at 22:39
• This is basically a proof that if $gcd(a,b) =1$ if and only if $a$ has a modular inverse $r$ which means that $ar \equiv 1 \text{ mod } b$ – flawr Aug 17 '14 at 22:41
• So you mean to say that it isn't possible? And is there no way to manipulate it (like divide a and b by the GCD in order to get a GCD of 1, and then undo it somehow at the end…)? – Jo.P Aug 17 '14 at 22:43

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

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.