# Math Help - Positive Integers

1. ## Positive Integers

How many positive integers less than 2007 are relatively prime to 1001?

2. Factor: $1001 = 7 \cdot 11 \cdot 13$.
How many positive integers less than 2007 are multiples of at least one of 7, 11, or 13? None of those integers can be relatively prime (also known as coprime) with 1001.

3. 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: . $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.