Results 1 to 2 of 2

Math Help - Relatively prime integers

  1. #1
    Newbie
    Joined
    Oct 2009
    Posts
    24

    Relatively prime integers

    Among n + 1 integers from 1, 2, . . . , 2n, can we prove that there are
    two which are relatively prime.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Apr 2010
    Posts
    33
    By the pigeonhole principle.

    Put the integers from 1 to 2n in bins, where each bin contains one integer and its successor.

    bin1 = {1,2}
    bin2 = {3,4}
    ...
    bin(n) = {2n-1,2n}

    There are n bins. If you take n + 1 integers from the set 1,2,...,2n, you are forced to take two integers from the same bin (pigeonhole). Since k and k + 1 are relatively prime, these two integers will be relatively prime.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Relatively Prime Quadratic Integers
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 29th 2010, 02:04 PM
  2. Relatively Prime Set of Integers
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: May 15th 2010, 01:32 AM
  3. Replies: 3
    Last Post: October 21st 2009, 08:58 PM
  4. Integers mod n is a field if and only if n is prime
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: August 30th 2009, 08:42 PM
  5. relatively prime integers....
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 16th 2008, 02:00 PM

Search Tags


/mathhelpforum @mathhelpforum