Results 1 to 5 of 5

Thread: sets and relatively prime integers

  1. #1
    Newbie
    Joined
    Oct 2009
    Posts
    22

    sets and relatively prime integers

    If $\displaystyle S$ is any set of $\displaystyle n + 1$ integers selected from $\displaystyle 1, 2, 3,\cdot\cdot\cdot,2n + 1$,

    prove that $\displaystyle S$ contains two relatively prime integers.
    Prove that the result does not hold if $\displaystyle S$ contains only $\displaystyle n$ integers.

    I think that the pigeonhole principle might be a way to prove this, but I don't know to determine what are the pigeons and what are the pigeonholes.

    Thanks for the help!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,796
    Thanks
    2827
    Awards
    1
    Quote Originally Posted by keityo View Post
    If $\displaystyle S$ is any set of $\displaystyle n + 1$ integers selected from $\displaystyle 1, 2, 3,\cdot\cdot\cdot,2n + 1$,
    prove that $\displaystyle S$ contains two relatively prime integers.
    Prove that the result does not hold if $\displaystyle S$ contains only $\displaystyle n$ integers.
    You need to notice that if $\displaystyle \{a,b\}\subseteq \{1,2,\cdots,2n+1\}$ then $\displaystyle \gcd(a,b)\le n-1$.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2009
    Posts
    22
    Why is then true?

    I just had an idea: if $\displaystyle S$ has only n integers, then the set $\displaystyle {2,4,6,\cdot\cdot\cdot,2n}$ will have n integers, and all will be not relatively prime, which proves the second statement.

    If $\displaystyle S$ has n+1 integers, then one of the integers must be odd because there can only be n even numbers in the set $\displaystyle {1,2,...,2n + 1}$ Thus, 2 and that odd number will be relatively prime, which proves the second statement.

    Is this proof ok?
    Thanks again.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Use the pigeon-hole principle! Amongst the following $\displaystyle n$ sets, there must be one containing two of your numbers :

    $\displaystyle \{1,2\}, \{3,4\},\hdots \{2n-1, 2n, 2n+1\}$

    Now just remark that any two integers which lie in the same part of this partition are relatively prime.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    For your second part: $\displaystyle \{2,4,6,8,...,2n\} $.
    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: Dec 29th 2010, 01:04 PM
  2. Relatively Prime Set of Integers
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: May 15th 2010, 12:32 AM
  3. Relatively prime integers
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Apr 26th 2010, 08:49 AM
  4. Replies: 3
    Last Post: Oct 21st 2009, 07:58 PM
  5. relatively prime integers....
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Mar 16th 2008, 01:00 PM

Search Tags


/mathhelpforum @mathhelpforum