Results 1 to 3 of 3

Math Help - Positive Integers

  1. #1
    Junior Member Dragon's Avatar
    Joined
    Oct 2006
    Posts
    63

    Positive Integers

    How many positive integers less than 2007 are relatively prime to 1001?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,617
    Thanks
    1581
    Awards
    1
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,713
    Thanks
    633
    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.

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 4
    Last Post: January 30th 2010, 03:59 AM
  2. if x and n are positive integers....
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: November 6th 2009, 11:07 PM
  3. Two Positive Integers....
    Posted in the Algebra Forum
    Replies: 6
    Last Post: May 20th 2007, 06:50 PM
  4. Sum of Positive Integers
    Posted in the Algebra Forum
    Replies: 4
    Last Post: March 31st 2007, 04:34 AM
  5. Positive Integers
    Posted in the Algebra Forum
    Replies: 1
    Last Post: January 28th 2007, 05:25 PM

Search Tags


/mathhelpforum @mathhelpforum