1

I'm given a problem stating:

If $\gcd(m,x) = 1$ then $x$ has a unique inverse modulo $m$.

I'm told to state and prove the converse, which I believe is:

$$ x \text{ has a unique inverse modulo } m \implies \gcd( m, x ) = 1$$

After that step I'm sort of stuck. I know for gcd to equal $1$ you must end up with:

$$ma + xb = 1$$

grg
  • 1,017
Jerry Baldwin
  • 51
  • Hint: any common divisor of $,m,x,$ divides the LHS of the final equation, so also the RHS $(= 1).\ $ That equation follows from the hypothesis that $,x,$ is invertible, i.e. $, xb\equiv 1\pmod{m},$ for some $,b.\ \ $ – Bill Dubuque Feb 11 '15 at 02:18

1 Answers1

1

Suppose $x$ has an inverse modulo $m$. Then for some integer $y$ we have $xy\equiv 1\pmod{m}$. Thus $xy-1=qm$ for some integer $q$.

Now we show that $\gcd(x,m)=1$. This follows from the fact that $(m)(-q)+(x)(y)=1$. If further details is needed, suppose that $d$ divides $x$ and $m$. Then from $(m)(-q)+(x)(y)=1$ we conclude that $d$ divides $1$. It follows that no $d\gt 1$ can be a common divisor of $x$ and $m$.

André Nicolas
  • 507,029
  • Thank you for the help. This makes a lot of sense to me. However, I don't quite understand d > 1. Does that insure that our inverse is unique? – Jerry Baldwin Feb 11 '15 at 02:44
  • You asked for a proof that if $x$ has a unique inverse modulo $m$ then $\gcd(x,m)=1$. I showed that if $x$ has an inverse then $\gcd(x,m)=1$. The uniqueness part was not necessary for the proof. If you were asked to prove that if $\gcd(x,m)=1$ then $x$ has a unique inverse, we would need to prove both existence and uniqueness. But it seems that the problem does not ask you to prove that $\gcd(x,m)=1$ implies unique inverse. The problem seems to concentrate only on the converse. – André Nicolas Feb 11 '15 at 02:53