# Integers satisfying condition - highest common factor of $(n,36)$ is $1$

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

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

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