# Invertible elements of $\mathbb Z/pq\mathbb Z$

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?

-
I 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 with which you can form a 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.] –  Dylan Moreland Feb 1 '12 at 16:42

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.

-
+1 for using $\perp$. –  user2468 Feb 1 '12 at 16:52

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

-