For every positive integer $n$, let $$A_n = \{a \in \mathbb{N} \mid 1 \leq a \leq n \mid gcd(a,n) = gcd(a+1, n) = 1\}$$ Evaluate $\mid A_n\mid$
- Assume that $n$ has the factorization $n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$. Then the answer is $$\mid A_n\mid\space = n\Bigg(1- \dfrac{2}{p_1}\Bigg)\Bigg(1-\dfrac{2}{p_2}\Bigg)\cdots\Bigg(1-\dfrac{2}{p_k}\Bigg)$$
- I think it can be proved similarly to the way we prove the formula of Euler function. But my teacher said that we can use the Chinese Remainder Theorem for this. And of course that will give us a beautiful solution. Can someone please help me?
Hint: The Chinese Remainder Theorem gives a surjection $$\phi:\mathbb Z/ n \mathbb Z \rightarrow \mathbb Z / p_1 \mathbb Z \times \cdots \times \mathbb Z / p_n \mathbb Z.$$
Let $x$ be an element of the codomain. Can you find conditions on the coordinates of $x$ that determine if $x \in \phi(A_n)$? Doing this should allow you to compute $|\phi(A_n)|$. If you know $|\ker \phi|$ and $|\phi(A_n)|$, can you compute $|A_n|$?
This method resembles common proofs of the formula for Euler's totient function (I guess that you've seen a different proof). Once you work out this problem with the CRT, it should be straightforward to adapt the method and prove the Euler's totient formula using the CRT.