Let $p,q$ two distinct primes. What are the invertible elements of $\mathbb{Z}/pq\mathbb{Z}$? I couldn't figure it out. I've got also a question about the notation, what is the logic behind $\mathbb{Z}/pq\mathbb{Z}$? I would think $\mathbb{Z}/pq$ would be much easier and logical?
Invertible elements of $\mathbb Z/pq\mathbb Z$
-
2I don't know about it being more logical, but people do write things like $\mathbb Z/pq$. I think the point is that "$pq$" is an element, not an [ideal](http://en.wikipedia.org/wiki/Two-sided_ideal) with which you can form a [quotient ring](http://en.wikipedia.org/wiki/Quotient_ring), but of course it's clear what you mean. $\mathbb Z/(pq)$ is also in use. [If you do not know what these words mean, then just ignore the notation for now.] – 2012-02-01
2 Answers
In general, for $\mathbb Z/m\mathbb Z$, the invertible elements are the ones that are coprime to $m$. This is a consequence of Bézout's theorem: if $x \perp m$ (I like to use $\perp$ to denote coprimality), then some $k,\ell$ exist such that $kx + \ell m = 1$ and in particular, $kx \equiv 1 \pmod m$.
For $m = pq$ the elements that are not coprime to $pq$ are the ones that are divisible by $p$ or $q$, these are $p, 2p, ..., qp = 0$ and $q,2q, ... , pq = 0$.
By the way, we see that there are $1 + (q-1) + (p-1) = p+q-1$ elements that are not invertible, thus the number of invertible elements is $pq -p-q+1 = (p-1)(q-1),$ consequent with $\phi(pq) = \phi(p)\phi(q) = (p-1)(q-1)$.
The notation comes from ring theory: $\mathbb Z/m\mathbb Z$ is the ring that arises by "dividing" or "modding out" the ideal $m\mathbb Z = \{0,\pm m, \pm 2m, \dots\}$ in the ring $\mathbb Z$. Informally this means we consider the same ring $\mathbb Z$, but set all elements of the ideal we mod out, these are all multiples of $m$ equal to zero. Wikipedia gives a precise definition.
As recalled in Myself's answer, one knows that Bezout's Identity implies that the invertible elements in $\Bbb Z/n\Bbb Z$ are the classes $\bar k\bmod n$ such that ${\rm GCD}(k,n)=1$, whatever $n$.
Another possible approach to your question is to work out the following two exercises:
Exercise 1: There is a ring isomorphism $\Bbb Z/pq\Bbb Z\simeq\Bbb Z/p\Bbb Z\times\Bbb Z/q\Bbb Z$.
Exercise 2: If $A$ and $B$ are two rings, then $(A\times B)^\times=A^\times\times B^\times$.
(if $R$ is a ring, the symbol $R^\times$ denotes the multiplicative group of invertible elements in $R$)