3
$\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$
4
  • 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$ Commented Aug 17, 2014 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$ Commented Aug 17, 2014 at 22:41
  • $\begingroup$ Use the extended-euclidean algorithm. It is an extension to the modular multiplicative inverse. $\endgroup$ Commented Aug 17, 2014 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$ Commented Aug 17, 2014 at 22:42

4 Answers 4

Reset to default
16
$\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$
1
  • $\begingroup$ well played bro $\endgroup$ Commented May 30, 2016 at 16:17
2
$\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$
3
  • $\begingroup$ Er…can you explain that a little more with regular words? I got lost in the symbols... $\endgroup$ Commented Aug 17, 2014 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$ Commented Aug 17, 2014 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$ Commented Aug 17, 2014 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$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.