# 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,

-

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

-
wow... thank you! I think I got it :) –  dashdart Aug 8 '12 at 17:24

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

-

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.)

-

Write down what it means for an integer to have an inverse modulo $n$, and recall Bézout's identity.

-