Number of integers whose gcd with 300 is 1

Question

Find the number of integers between 1 and 300 (including the ends) whose gcd with 300 is 1.

What happens when when $'1'$ is changed to $'2'$?

My try:

Write $300$ as $2*2*3*5*5$

The required answer will be all the prime numbers between 5 and 300(is it correct?)

For second part I have no idea how to proceed

Will it be those numbers which have just 2 or multiples of 2 as factors(not 3 and 5)?

We can calculate numbers which are divisible by 3 and 5 till 300 and subtract it from 300.

Any help will be appreciated

Answer 1

The number you ask for is called the totient of $300$, written $\varphi(300)$. It can be shown that if $n = p_1^{\alpha_1} p_2^{\alpha_2} \dotsm p_k^{\alpha_k}$ where $p_i$ are primes and $\alpha_i > 0$, then:

$$\varphi(n) = n \cdot \left( 1 - \frac{1}{p_1} \right) \cdot \left( 1 - \frac{1}{p_2} \right) \dotsm \left( 1 - \frac{1}{p_k} \right)$$

In your case, $300 = 2^2 \cdot 3 \cdot 5$, so

$$\varphi(300) = 300 \cdot \left( 1 - \frac{1}{2} \right) \cdot \left( 1 - \frac{1}{3} \right) \cdot \left( 1 - \frac{1}{5} \right) = 80$$