How many positive integers less than 2007 are relatively prime to 1001?
Hello, Dragon!
How many positive integers less than 2007 are relatively prime to 1001?
There are 2006 positive integers less than 2007.
How many of these have a common factor with 1001?
We find that: .$\displaystyle 1001 \:=\:7\!\cdot\!11\!\cdot\!13$
There are: .$\displaystyle \left[\frac{2006}{7}\right] = 286$ with a factor of 7.
There are: .$\displaystyle \left[\frac{2006}{11}\right] = 182$ with a factor of 11.
There are: .$\displaystyle \left[\frac{2006}{13}\right] = 154$ with a factor of 13.
There are: .$\displaystyle \left[\frac{2006}{77}\right] = 26$ with a factor of 7 and 11.
There are: .$\displaystyle \left[\frac{2006}{91}\right] = 22$ with a factor of 7 and 13.
There are: .$\displaystyle \left[\frac{2006}{143}\right] = 14$ with a factor 11 and 13.
There are: .$\displaystyle \left[\frac{2006}{1001}\right] = 2$ with a factor of 7, 11 and 13.
Formula:
$\displaystyle n(A\,\cup B\,\cup\ C) \;=\;n(A) + n(B) + n(C) - n(A\,\cap\,B) - n(A\,\cap\ C)$ $\displaystyle - n(B\,\cap\,C) + n(A\,\cap\,B\,\cap\,C)$
Hence: .$\displaystyle n(7 \cup 11 \cup 13) \;=\;286 + 182 + 154 - 26 - 22 - 14 + 2 \;=\;562$
There are 562 integers which have factors of 7, 11, and/or 13.
Therefore, there are: .$\displaystyle 2006 - 562\:=\:1444$ integers relatively prime to 1001.