0

I am having hard time understanding the questions and I can't think of any way to solve it, it's a question from a competitive test.

Iti Shree
  • 1,476
  • Well, for a start you can start by considering all the prime numbers from 1 to 100. Then proceed to find all composite number from 1 to 100 s.t. the hcf with 36 is 1. A useful hint is to consider the prime factorization of 36 = 2^2 × 3^2. – Soby Apr 19 '17 at 18:37
  • Ok I'll try. Thanks but sorry it's 1000 actually. – Iti Shree Apr 19 '17 at 18:42
  • The usual method will still hold. More explicitly, since 36 = 2^2 × 3^2, the numbers you want to find must not contain 2 or 3 in its prime factorization. In other words it may contain other primes such as 5,7, 11,etc... One example is 5^2 × 7 = 175. Can you take it from here? – Soby Apr 19 '17 at 18:47
  • See this https://en.wikipedia.org/wiki/Euler%27s_totient_function – Jaideep Khare Apr 19 '17 at 18:54

2 Answers2

3

As the prime factors of $36$ are $2$ and $3$, the integers coprime to $36$ are of the form $6k+1$ and $6k+5$. The largest $6k+1$ that is less than $1000$ is $997$. How many $6k+1$s are there? Then for $6k+5 \ldots$

Ross Millikan
  • 374,822
0

$36 = 2^2\times 3^2$. Any number which is divisible by neither $2$ nor $3$ satisfies the property in question. There are $50$ numbers divisible by $2$, and $33$ numbers divisible by $3$. The numbers divisible by $6$ ($16$of them) are counted twice, so the result is $100 - 50 - 33 + 16 = 33$

user58697
  • 2,761