5
$\begingroup$

I'm having trouble understanding why for finding the inverse for $x\bmod n$, $\gcd(x, n)=1$ is a precondition. Obviously I've tried examples where the gcd is greater than one and I can't find $a$ for $ax \equiv _n 1$. I'm trying to prove to myself why this is the case.

I can mechanically say the following:

Find the modular inverse $a$ of $x\pmod n$

$$ax \equiv _n 1 \Leftrightarrow n \mid (ax-1)$$

And $n \mid (ax-1)$ implies that $(ax-1)=nk$ for some $k \in \mathbb Z $

After that I am stuck and I'm not sure if I'm going in the right direction.

$\endgroup$
  • $\begingroup$ This connected to Bezout identity : two given integers $a$ and $b$ are coprime iff there exist two integers $r,s$ such that $ra+sb=1$. $\endgroup$ – Adren Jan 17 '17 at 4:55
  • $\begingroup$ @Adren sure, that gives another definition but I don't understand why it works the way it does $\endgroup$ – Carpetfizz Jan 17 '17 at 4:57
  • $\begingroup$ In your final equation add one to both sides and subtract $nk$ then suppose the gcd(x,n) > 1. $\endgroup$ – Crenner Jan 17 '17 at 4:58
  • $\begingroup$ @Crenner I'm dumb, $ax - nk = 1$, still don't see it... $\endgroup$ – Carpetfizz Jan 17 '17 at 5:05
  • 1
    $\begingroup$ $ax-nk$ is a multiple of the gcd (x,n). $\endgroup$ – fleablood Jan 17 '17 at 5:52
8
$\begingroup$

If there is an inverse of $x \bmod n$, that gives us a number $y$ so that $xy \equiv 1 \bmod n$. That means that $xy=kn+1$, or (rearranging) that $xy-kn=1$.

Now for any common divisor, $c$, of $x$ and $n$ we will have that $c \mid (xy-kn)$ which gives $c\mid 1$, that is, $c=1$. So that is an outcome - and therefore a requirement - of finding the inverse of $x \bmod n$

$\endgroup$
  • $\begingroup$ This was very clear thank you. So why is it that such an outcome becomes a requirement? We didn't necessarily work backwards from saying "let's find a $gcd(x,n) >1$ and see if it breaks" but rather show that it has to be $1$. $\endgroup$ – Carpetfizz Jan 17 '17 at 5:08
  • $\begingroup$ I said at the start - IF we can find an inverse, that will lead to $\gcd(x,n)=1$. So if $\gcd(x,n)$ is not $1$, we won't be able to find an inverse. Does that make sense? $\endgroup$ – Joffan Jan 17 '17 at 5:10
  • $\begingroup$ yeah thanks, I think I'm stuck in a circular reasoning which is my fault. I'm going to work through this slowly $\endgroup$ – Carpetfizz Jan 17 '17 at 5:17
  • 1
    $\begingroup$ Yes, I think you probably have the idea. $c=1$ is a condition of the existence of inverse $y$ (because we know that finding a $y$ will inevitably mean that $c=1$), and if $c\ne1$ then we don't need to bother looking for $y$ because it can't exist. However it's not quite a strong as you have phrased it (that's a different proof) - what I wrote above doesn't actually force the existence of an inverse for every $c=1$. $\endgroup$ – Joffan Jan 17 '17 at 5:29
  • 1
    $\begingroup$ They mean that if we can find two numbers $y_1$ and $y_2$ such that $xy_1\equiv 1$ and $xy_2\equiv 1 \bmod n$, then $y_1\equiv y_2 \bmod n$. That's not too hard to prove: $xy_1\equiv xy_2 \bmod n$ so $n$ divides $(xy_1- xy_2)=x(y_1- y_2)$. We know that $n$ doesn't share any factors with $x$ so then $n\mid (y_1-y_2)$ and $y_1\equiv y_2 \bmod n$. $\endgroup$ – Joffan Jan 17 '17 at 5:49
5
$\begingroup$

Another way to see that this reveals something interesting about the structure of fields.

If $\gcd(n,x)=c$ then we can look at $y=\frac{x}{c}$. Clearly $xy=n$, but then $xy=0\pmod{n}$. For $c\neq 1$, this makes $x$ a zero-divisor - a number that isn't zero that when multiplied by another non-zero number gives zero. We can see that zero divisors aren't invertable (in general, not just in modular arithmetic) as follows:

Take $ab=0$ for $a,b\neq 0$. Assume $\exists a^{-1}$ such that $a^{-1}a=1$. Then $b=a^{-1}ab=a^{-1}0=0$ which is a contradiction since we assumed that $a,b\neq 0$.

It turns out that being a zero divisor exactly encapsulates what it means to be non-invertable, as show by the following theorem:

Theorem: Let $(R, +,\cdot)$ be a ring with identity. Then $(R,+\cdot)$ is a field if and only if $R$ contains no zero divisors.

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