Number of integers $n$ between 1 and 1000 such that the HCF of $n$ and $36$ is 1

Question

How many integers $n$ are there such that $1< n < 1000$ and the highest common factor of $n$ and $36$ is $1$?

I have tried counting the prime numbers up to $1000$ using the prime-counting function. But there are of course other numbers like $133$, $77$ which are not prime and yet they satisfy the conditions.

Is there any efficient algorithm to solve this problem?

Answer 1

In order for the greatest common factor of an integer $n$ and $36$ to be $1$, $n$ and $36$ must share no prime divisors. The prime divisors of $36$ are $2$ and $3$.

Thus, the question now becomes:

How many integers $1 \leq n \leq 1000$ are not multiples of $2$ or $3$?

This is fairly easy to compute by looking at the compliment and utilizing the inclusion/exclusion principle --- let $m_k$ be the number of multiples of $k$ between $1$ and $1000$: \begin{equation} \mathrm{nonmultiples} = 1000 - \left(m_2 + m_3 - m_6\right) \end{equation}

It can also be seen that the value of $m_k$ is $\left\lfloor\frac{1000}{k}\right\rfloor$.

Answer 2

Since $36 = 2*2*3*3$, $\gcd(n,36) = 1$ iff $n$ is not divisible by $2$ or $3$. Hence

First we find the number of integers $< 1000$ which are divisible by $2$ or $3$. The we will subtract this number from $999$ to get our required answer.

No. of integers $< 1000$ which are divisible by $2 = [999/2] = 499$

No. of integers $< 1000$ which are divisible by $3 = [999/3] = 333$

But some numbers which are divisible by both $2$ and $3$ i.e. multiples of $6$. So to avoid double counting we need to subtract these multiples of $6$

No. of integers $< 1000$ which are divisible by $6 = [999/6] = 166$

Hence No. of integrs $< 1000$ which have $HCF > 1$ with $36 = 499 + 333 - 166 = 666$

Hence No. of integrs $< 1000$ which have $HCF = 1$ with $36 = 999 - 666 = 333$