0
$\begingroup$

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$

  1. 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)$$
  2. 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?
$\endgroup$
4
  • $\begingroup$ If $n$ is even then $|A_n|=0$. If $n$ is prime then $|A_n|=n-2$. $\endgroup$ Commented Jul 23, 2014 at 15:12
  • $\begingroup$ Yeah, I forgot the case $n$ is even. The above answer is for case $n$ is odd. $\endgroup$ Commented Jul 23, 2014 at 15:22
  • $\begingroup$ Your formula works for $n$ even. If $A_n$ is empty, it has size zero. On the other hand, from your formula you get zero, since one of the prime factors is $2$ and so one of the terms in your product is $1 - \frac{2}{2}=0$. $\endgroup$ Commented Jul 23, 2014 at 15:23
  • $\begingroup$ This formula is quoted in oeis.org/A058026 . $\endgroup$ Commented May 13 at 13:23

1 Answer 1

Reset to default
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.