# Does the Chinese Remainder Theorem hold for "incongruence" equations?

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?

• 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/… Oct 13 '20 at 4:07
• Thank you! This proof is a really helpful reference. 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.