2
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Why are we including the multiples of 6.? Actually I cannot fully understand the solution. $\endgroup$ – Ayus Das Jun 18 at 4:54
  • 2
    $\begingroup$ @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. $\endgroup$ – Shubham Johri Jun 18 at 6:58
  • $\begingroup$ I have understood. Thanks $\endgroup$ – Ayus Das Jun 18 at 7:52
3
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ Ok. I understood this $\endgroup$ – Ayus Das Jun 18 at 4:51
  • 2
    $\begingroup$ 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$. $\endgroup$ – John Omielan Jun 18 at 5:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.