Thread: Positive Integers

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

Factor: $\displaystyle 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.

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.