# Proving multiplicative inverse of modulo $m$ exists when $\gcd(m,x)=1$ [duplicate]

I basically don't understand the way the proof is given in my text as well as some references online. They basically do the same thing.

THEOREM: Let $$m,x$$ be positive integers such that $$\gcd(m, x) = 1$$. Then $$x$$ has a multiplicative inverse modulo $$m$$, and it is unique, $$\mod m$$.

Now, this is a sufficient and necessary condition, but let's just look at the proof that it is the sufficient condition which is given in my texts.

Proof:
Consider the sequence of m numbers $$0,x,2x,...,(m−1)x$$. We claim that these are all distinct,$$\mod m$$. Since there are only $$m$$ distinct values modulo $$m$$, it must then be the case that $$ax = 1 \mod m$$, for exactly one $$a (\mod m)$$. This a is the unique multiplicative inverse. To verify the above claim, suppose that $$ax = bx \mod m$$ for two distinct values $$a,b$$ in the range $$0 ≤ a,b ≤ m−1$$. Then we would have $$(a−b)x = 0 \mod m$$, or equivalently, $$(a−b)x = km$$ for some integer $$k$$ (possibly zero or negative). But since $$x$$ and $$m$$ are relatively prime, it follows that $$a−b$$ must be an integer multiple of $$m$$. This is not possible since $$a,b$$ are distinct non-negative integers less than $$m$$.

What I don't see particularly in this proof is the connection betweent the $$\gcd$$ being one and the existence of the multiplicative inverse. What I do see instead is that the proof that the multiplicative inverse is unique.

What is the connection of the $$\gcd$$ being $$1$$ and the existence of the multiplicative inverse $$\mod m$$?

• You may find illuminating the $4$ equivalent characterizations in the Theorem here. – Bill Dubuque Feb 24 at 14:37
• – Bill Dubuque Feb 24 at 15:24

The above proof shows that the set $$\{0,x,2x,\dots,(m−1)x\}=\{ax \mid a = 0,\dots,m-1\}$$ has distinct elements under $$\mod{m}$$. Therefore, $$|\{0,x,2x,\dots,(m−1)x\}| = m$$, therefore, this set under $$\mod{m}$$ contains all representatives in $$\mod{m}$$. In particular, there exists $$a \in \Bbb{Z}$$ such that $$ax \equiv 1 \pmod{m}$$, so there exists $$k \in \Bbb{Z}$$ such that $$ax = 1 + km$$. This should give you $$ax - km = 1$$, so that $$\gcd(a,m) = 1$$ by Bezout's Identity.
The key is in the claim that $$0, x, 2x, \ldots, (m-1)x$$ are all distinct. If this weren't true then $$(a-b)x = km$$ for some $$a,b and some integer $$k$$. This says that $$m$$ divides $$(a-b)x$$. Since $$x$$ and $$m$$ are relatively prime, $$m$$ must divide $$a-b$$.
It might help to think in terms of prime factorization. If $$m$$ divides $$(a-b)x$$ then all of the prime powers in $$m$$ must live in the product $$(a-b)x$$. $$m$$ and $$x$$ being relatively prime says that none of the primes dividing $$m$$ divide $$x$$, so all of the prime powers making up $$m$$ must come from $$(a-b)$$. This shows that $$m$$ divides $$a-b$$. Does the rest of their proof make sense?
• "Relatively prime" means the same thing as having a GCD of 1. The conclusion that $m$ divides $a-b$ comes from the GCD being 1 (in the way I described above). Once you have that $0, x, 2x, \ldots, (m-1)x$ are distinct, you must have that $ax \equiv 1\pmod{m}$ for some $a$. – Liam Feb 24 at 7:57