2
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – Jack D'Aurizio Aug 17 '14 at 22:34
  • $\begingroup$ I'm not quite sure I understand you. Can you please explain more specifically where the mistake is that you are pointing out? $\endgroup$ – Jo.P Aug 17 '14 at 22:41
  • $\begingroup$ Use the extended-euclidean algorithm. It is an extension to the modular multiplicative inverse. $\endgroup$ – Ryan Aug 17 '14 at 22:42
  • 1
    $\begingroup$ 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$). $\endgroup$ – Dan Rust Aug 17 '14 at 22:42
10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ well played bro $\endgroup$ – rakeb.mazharul May 30 '16 at 16:17
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Er…can you explain that a little more with regular words? I got lost in the symbols... $\endgroup$ – Jo.P Aug 17 '14 at 22:39
  • $\begingroup$ 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$ $\endgroup$ – flawr Aug 17 '14 at 22:41
  • $\begingroup$ 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…)? $\endgroup$ – Jo.P Aug 17 '14 at 22:43
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.