Numbers of relatively primes

2,043

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

Share:
2,043

Related videos on Youtube

blastzit
Author by

blastzit

Updated on August 15, 2022

Comments

  • blastzit
    blastzit 2 months

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