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

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?

## 2 Answers

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

• Why are we including the multiples of 6.? Actually I cannot fully understand the solution. – Ayus Das Jun 18 at 4:54
• @AyusDas Since some numbers are multiples of both $2$ and $3$ i.e. multiples of $6$. They are included in both $m_2,m_3$. The formula is a direct consequence of inclusion-exclusion. – Shubham Johri Jun 18 at 6:58
• I have understood. Thanks – Ayus Das Jun 18 at 7:52

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$$

• Ok. I understood this – Ayus Das Jun 18 at 4:51
• Your answer says "No. of integers $< 1000$ which are divisible by $2 = [999/2]+1 = 499$". The "$+1$" part should be removed as it's incorrect. Also, I believe that using square brackets is the not the standard way to indicate the largest integer operation. Instead, I suggest using the floor function, e.g., $\lfloor 999/2 \rfloor$. – John Omielan Jun 18 at 5:24