# Proving that modular inverse only exists when $\gcd(n,x)=1$

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.

• 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$. – Adren Jan 17 '17 at 4:55
• @Adren sure, that gives another definition but I don't understand why it works the way it does – Carpetfizz Jan 17 '17 at 4:57
• In your final equation add one to both sides and subtract $nk$ then suppose the gcd(x,n) > 1. – Crenner Jan 17 '17 at 4:58
• @Crenner I'm dumb, $ax - nk = 1$, still don't see it... – Carpetfizz Jan 17 '17 at 5:05
• $ax-nk$ is a multiple of the gcd (x,n). – fleablood Jan 17 '17 at 5:52

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$

• 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$. – Carpetfizz Jan 17 '17 at 5:08
• 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? – Joffan Jan 17 '17 at 5:10
• yeah thanks, I think I'm stuck in a circular reasoning which is my fault. I'm going to work through this slowly – Carpetfizz Jan 17 '17 at 5:17
• 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$. – Joffan Jan 17 '17 at 5:29
• 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$. – Joffan Jan 17 '17 at 5:49

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.