Here's a problem I saw recently:
How many of the integers $n$ with $1\leq n\leq 150$ are relatively prime to $70$?
Can someone help me with it? Thanks!
EDIT: Here's my approach to this problem:
My attempt:
Notice that $70=2\times5\times7$. Hence if $n=p_1p_2p_3...p_n$ and $\gcd{(n, 70)}=1$, then $p_1,p_2,p_3,...,p_n$ must not be $2$, $5$, or $7$.
From here on I don't know what to do except for listing all the numbers out. :(
The prime factors of $70$ are $2,5$ and $7$.
Use inclusion/exclusion principle in order to calculate the amount of numbers in the range $[1,150]$ that are not divisible by either one of these prime factors:
$$150-\left\lfloor\frac{150}{2}\right\rfloor-\left\lfloor\frac{150}{5}\right\rfloor-\left\lfloor\frac{150}{7}\right\rfloor+\left\lfloor\frac{150}{2\cdot5}\right\rfloor+\left\lfloor\frac{150}{2\cdot7}\right\rfloor+\left\lfloor\frac{150}{5\cdot7}\right\rfloor-\left\lfloor\frac{150}{2\cdot5\cdot7}\right\rfloor$$