Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
up vote 3 down vote accepted

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

share|cite|improve this answer
wow... thank you! I think I got it :) – funktor 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}$.

share|cite|improve this answer

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

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.