For a discrete math course I'm taking, I was solving the following question:

Given that $\mathbb{Z}_{n}^{*}=\left\{a \in \mathbb{Z}_{n} \mid g \operatorname{cd}(a, n)=1\right\} . \text { Let } \varphi(n)=\left|\mathbb{Z}_{n}^{*}\right|$, show that for every $n$, we have $\varphi(n) = n \prod_{primes\ p|n} \left(1 - \frac{1}{p}\right)$

My approach was as follows:

Let $\mathbb{P}_i$ be the multiset whose elements represent the prime factorization of i. Then, the set $\mathbb{Z}_{i}^*$ is composed of elements, $x$ which satisfy $x \not\equiv 0 \text{ (mod p) } \forall p \in \mathbb{P}_i, x \in \mathbb{Z}_i$. By the Chinese Remainder Theorem, because the elements p are prime, and thus by definition also pairwise coprime, the total number of elements in $\mathbb{Z}_{i}^*$ is the product of the number of solutions for each congruence (mod p). The number of solutions to the congruence for a prime number $p$ for $x \in \mathbb{Z}_{n}$ is given by $n \left(1 - \frac{1}{p}\right)$ (shown in a different part of the problem set). This directly gives the desired expression.

My question is:

Is my application of the Chinese Remainder Theorem valid? Does the Chinese Remainder Theorem apply for "incongruence" expressions as well as congruence expressions? If it is invalid, how can I correct the proof to account for this?

  • 1
    $\begingroup$ I'm not quite able to follow your argument, so I'm unsure if it is valid. I've written out how I use the CRT to prove the underlying theorem. See the addendum re math.stackexchange.com/questions/3858851/… $\endgroup$ Oct 13 '20 at 4:07
  • $\begingroup$ Thank you! This proof is a really helpful reference. $\endgroup$ Oct 13 '20 at 4:12

Well, it's not clear what you mean by the "incongruence" version of the Chinese remainder theorem.

But one thing we can definitely say is the following. Say we know $x \not\equiv 0 \pmod{p_1}$, $x \not\equiv 0 \pmod{p_2}$, and so on. Then there are $p_1 -1$ options for what $x$ could be modulo $p_1$; $p_2 - 1$ options modulo $p_2$, and so on.

For every one of the $(p_1 - 1)(p_2-1)\cdots$ combinations $(b_1, b_2, \dots)$ of these options, you could write down the equations $x \equiv b_1 \pmod{p_1}$, $x \equiv b_2 \pmod{p_2}$, and so on. Here, the ordinary Chinese remainder theorem applies, telling us that there is a unique answer modulo $p_1p_2\cdots$.

We need a slightly different (but very similar) argument when higher powers of a prime divide $n$, so watch out for that.


Clearly for prime $p$ we have $\varphi(p^n)=p^n(1-1/p)$, by counting.

But, by CRT, $\varphi$ is multiplicative. That is, $(m,n)=1\implies \varphi(mn)=\varphi(m)\cdot\varphi(n)$.

The result follows.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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