Counting problem(principle of inclusion and exclusion)

Question

Let C(n) denote the number of integers that are coprime to n from 1 to n, determine the value of C(36) and C(900)

Please lend me a hand, I know principle of inclusion and exclusion but I can't figure a way to use it. Thank you in advance

Answer 1

I'll compute $C(60)$ for you. Since $60=2^2*3*5$, we only have to consider the three primes $2$, $3$, and $5$. It is easier to compute the number of factors which are not coprime to $60$ and then subtract.

There are $\frac{60}{2}=30$ integers less than or equal to $60$ which are divisible by $2$ (and hence are not coprime to $60$).

There are $\frac{60}{3}=20$ integers less than or equal to $60$ which are divisible by $3$ (and hence are not coprime to $60$).

There are $\frac{60}{5}=12$ integers less than or equal to $60$ which are divisible by $5$ (and hence are not coprime to $60$).

The sum of these three is $62$ which is greater than the number of integers less than or equal to $60$, so obviously, some over-counting has occurred.

There are $\frac{60}{6}=10$ integers less than or equal to $60$ which are divisible by $2\cdot 3$ (and hence are overcounted).

There are $\frac{60}{10}=6$ integers less than or equal to $60$ which are divisible by $2\cdot 5$ (and hence are overcounted).

There are $\frac{60}{15}=4$ integers less than or equal to $60$ which are divisible by $3\cdot 5$ (and hence are overcounted).

Now, there are two integers less than or equal to $60$ which are divisible by all three of $2$, $3$, and $5$; they are $30$ and $60$.

Then, using the inclusion-exclusion principle, there are $$(30+20+12)-(10+6+4)+2=62-20+2=44$$ integers less than or equal to $60$ which are not coprime to $60$. This leaves $16$ integers which are coprime to $60$.

Alternative hint: this is Euler's totient function, which is multiplicative and has a closed form.

Answer 2

Hint: If $p_1,\ldots,p_m$ are the prime divisors of $n$. Start with $n$. Now you need to exclude all the multiples of $p_1,\ldots,p_m$ smaller than or equal to $n$. But you've excluded twice the multiples of $p_ip_j$ for $i,j = 1,\ldots, m$ where $i\neq j$, so include those. Now you've included once too many times the multiples of $p_ip_jp_k$, so exclude those. Continue until you include/exclude the multiples of $p_1\cdot\ldots\cdot p_m$.