Proving multiplicative inverse of modulo $m$ exists when $\gcd(m,x)=1$ 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$?
 A: 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.
A: 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<m$ 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?
