Trouble relating the two definitions of $(\mathbb Z/n\mathbb Z)^\times$ I am having trouble relating the two definitions of $(\mathbb Z/n\mathbb Z)^\times$, the collection of residue classes having a multiplicative inverse in $(\mathbb Z/n\mathbb Z)$; and apparently, $(\mathbb Z/n\mathbb Z)^\times$ is a pretty important subset of $(\mathbb Z/n\mathbb Z)$ (please don't tell me what it is though, I'd like to know it myself!)
The "standard" definition (so-to-speak) goes something like this:
$$(\mathbb Z/n\mathbb Z)^\times=\{ \bar{a}\in\mathbb Z/n\mathbb Z : \exists \bar{c}\in \mathbb Z/n\mathbb Z ~\text{ where } \bar a . \bar c=\bar 1\}$$
The other one, the one that I am having trouble with, is this:
$$(\mathbb Z/n\mathbb Z)^\times=\{ \bar{a}\in\mathbb Z/n\mathbb Z : \gcd(a,n)=1\}$$

So how come that these two things are the same? Even more so, how do I prove that these two definitions are the same thing?

Any help is much Appreciated,
Thanks in advance!
 A: If $\overline{a}\cdot \overline{b}= \overline{1}$ then there is $k \in \mathbb{Z}$ such that $ab+kn=1$, therefore $\gcd(a,n)=1$. 
Conversely, let $a \in \mathbb{Z}$ such that $\gcd(a,n)=1$.Using Euclid's algorithm one can find $b,k \in \mathbb{Z}$ satisfying $ab+kn=1$, so $\overline{a}\cdot \overline{b}=\overline{1}$. 
A: The standard proof is listed in the above comments, here is an alternate self contained complete proof.
Suppose $\overline{a}\cdot \overline{c}=1$. Then $n|ac-1$. Let $d=\gcd(a,n)$. Then
$d|n|ac-1$ and $d|c|ac$ thus $d|ac$ and $d|ac-1$. This implies that $d| (ac)-(ac-1)$, and hence $d|1$.
Now for the other direction. Suppose that $\gcd(a,n)=1$.
Look at $\overline{a}, \overline{a^2},...,\overline{a^{n+1}}$. By the pigeon hole principle, two of them are equal. Thus, there exists $1 \leq i < j \leq n+1$ so that
$$ \overline{a^i}= \overline{a^j} \Rightarrow n|a^j-a^i=a^{i}(a^{j-i}-1)$$
Since $n| a^{i}(a^{j-i}-1)$ and $a$ si relatively prime to $a$, it follows that $n |a^{j-i}-1$, or
$$  \overline{a^{j-i}}=1$$
Now, set $c=a^{j-i-1}$ and you are done (note that $j-i-1 \geq 0$ so the definition of $c$ makes sense.)
A: Hint $\ $ Over $\,\Bbb Z\,$ (or any $\rm\color{#C00}{Bezout}$ domain $\rm\,Z)\,$ we have
$$\rm gcd(a,b) = 1\color{#C00}{\iff} \exists\, j,k\in Z\!:\ j\,a + k\,b = 1\iff \exists\, j\in Z\!:\ j\,a \equiv 1\,\ (mod\ b)$$ 
Remark $\ $ The key fact is that not only do gcds exist, but they have linear form - the characteristic property of a Bezout domain. Said ideally, two-generated ideals are principal $\rm\:(a,b) = (c),\:$ which is equivalent to saying that $\rm\:c\:$ is a linear common divisor of $\rm\:a,b,\:$ i.e. a common divisor that is also a $\rm\,Z$-linear combination $\rm\, c = j\,a+k\,b\:$ for $\rm\:j,k\in Z.\:$ Therefore, by induction, every finitely generated ideal is principal $\rm\:(a_1,\ldots,\,a_n) = (a),\:$ where $\rm\:a = gcd(a_1,\ldots,a_n).$
A: Write down what it means for an integer to have an inverse modulo $n$, and recall Bézout's identity.
