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?
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.