Positive Integers

**Dragon** · May 31st 2007, 01:58 PM

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

**Plato** · May 31st 2007, 02:32 PM

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.

**Soroban** · May 31st 2007, 02:48 PM

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.

Thread: Positive Integers

LinkBack

Thread Tools

Display

Positive Integers

Similar Math Help Forum Discussions

given positive integers a and b such that a|b^2, b^2|a^3, a^3|b^4,...

if x and n are positive integers....

Two Positive Integers....

Sum of Positive Integers

Positive Integers

Search Tags