Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
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

2 Answers 2

up vote 8 down vote accepted

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.

share|improve this answer
    
+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$)

share|improve this answer

Your Answer

 
discard

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.