-1
$\begingroup$

How many integers $n$ in the range of $2 \leq n \leq 1000$ which satisfies the following condition
Highest common factor of $(n,36)$ is $1$?

$\endgroup$
  • $\begingroup$ Brute force: 332 ;) $\endgroup$ – Dolma Apr 16 '13 at 14:18
  • $\begingroup$ @Dolma: It should be $333$ ? $\endgroup$ – Inceptio Apr 16 '13 at 14:44
  • $\begingroup$ @Inceptio 332 is correct. $\endgroup$ – Zero Apr 16 '13 at 14:55
  • $\begingroup$ @JohnGalt: Yes. Figured it now. $\endgroup$ – Inceptio Apr 16 '13 at 14:59
1
$\begingroup$

Hint: what are the prime factors of $36$? You are searching for numbers that have none of these. Since multiples of $6$ are important here (why?) maybe it would help to count by hand the ones up to $12$ and look for a pattern.

$\endgroup$
0
$\begingroup$

Hint:

Last number divisible by $36$ less than $1000$ is $972=36 \cdot 27$, calculate $\phi(972)$. Then find the co-primes of $36$ greater than $972$, that won't be hard. Use can use $\Phi$ function calculator, else it is just a matter of Inclusion-exclusion principal.

$\endgroup$
0
$\begingroup$

A number is prime to 36, if it doesn't contain 2 or 3, because 36=2x2x3x3. So all we need to do is search for a number which is nearest to 1000, and is made up of 2s and 3s and some big prime number. "Big" so that we can later on manually exclude the effect of that big number.

If you keep going backwards from 1000, i.e. 999, 998, and so on you will not find any such number. But 1002 is good enough because 1002= 2x3x167. So all you have to do is calculate ϕ(1002), and exclude all multiples of 167 (this is that big prime!) which doesn't contain 2, or 3. So we need not bother ourselves with 2x167, 3x167, 4x167, but we need to care about 5x167, because it is prime to 36, and it has been excluded from ϕ(1002), so we will have to include that manually in our list of co-primes with 36. And again 6x167=1002 is outside our requirement, and it has been included. Also ϕ(1000) counts the number 1 as one of the co-primes, so we need to exclude that. So, ϕ(1002)=332-1(Exclusion of the number 1)+1(Manual inclusion due to 167x5)=332

$\endgroup$

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.