Positive Integers

Hello, Dragon!

Quote:

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: . $1001 \:=\:7\!\cdot\!11\!\cdot\!13$

There are: . $\left[\frac{2006}{7}\right] = 286$ with a factor of 7.

There are: . $\left[\frac{2006}{11}\right] = 182$ with a factor of 11.

There are: . $\left[\frac{2006}{13}\right] = 154$ with a factor of 13.

There are: . $\left[\frac{2006}{77}\right] = 26$ with a factor of 7 and 11.

There are: . $\left[\frac{2006}{91}\right] = 22$ with a factor of 7 and 13.

There are: . $\left[\frac{2006}{143}\right] = 14$ with a factor 11 and 13.

There are: . $\left[\frac{2006}{1001}\right] = 2$ with a factor of 7, 11 and 13.

Formula:

$n(A\,\cup B\,\cup\ C) \;=\;n(A) + n(B) + n(C) - n(A\,\cap\,B) - n(A\,\cap\ C)$ $- n(B\,\cap\,C) + n(A\,\cap\,B\,\cap\,C)$

Hence: . $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: . $2006 - 562\:=\:1444$ integers relatively prime to 1001.