1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Pigeon Hole Principle problem

  1. Apr 6, 2010 #1
    1. The problem statement, all variables and given/known data
    Using pigeon hole principle, prove that if m and n are relative prime integers and a and b are any integers, there exists an integer x such that x = a mod m, and x = b mod n.


    2. Relevant equations
    none


    3. The attempt at a solution
    data: m|(x -a) and n|(x-b)
    hence we can write, for some integers p and q
    x = pn + a and x = qm + b

    also, since (m,n) = 1, there are integers i and j such that
    im + jn = 1

    how do we apply the pigeon hole principle to this problem?
     
    Last edited: Apr 7, 2010
  2. jcsd
  3. Apr 6, 2010 #2
    Hello,
    I think I have a solution, but I am not sure, especially because I haven't used the pigeonhole principle:(By the way: Some things you list under data (x=pm+a etc), you have to show that, that isn't given.)

    We can always say that there is a x such that x=pn+a (for some p). ( Notice your typo.) Oh, by the way: We haven't yet fixed the value of this p.
    We have to show that (pn+a)-b=qm, for some q. Or in other words: a-b=pn-qm . Well, as gcd(n,m)=1, we can ALWAYS find p and q such that pn-qm equals any value, in particular a-b.
     
  4. Apr 7, 2010 #3
    Hey mathmadx,
    I am not aware of this result you have used,

    "Well, as gcd(n,m)=1, we can ALWAYS find p and q such that pn-qm equals any value, in particular a-b. "

    What I do know is,
    "If a and b are integers, not both 0, then gcd(a,b) exists; and we can find integers m and n such that gcd(a,b) = ma + nb."

    In this case, as I have stated, there exists integers i and j such that
    im + jn = 1

    Are you sure that your statement is true?

    PS: I have edit my first post to fix the typo.
     
  5. Apr 7, 2010 #4
    Hi,
    I figured it out, yeah I guess we can always find p and q such that pn - qm equals any value.

    Since we can find i and j such that
    im + jn = 1

    (a-b)im + (a-b)jn = (a-b)

    hence our p and q would be (a-b)j and -(a-b)m.

    Still don't know how Pigeon hole principle is used here though.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Pigeon Hole Principle problem
  1. Pigeon hole principle (Replies: 3)

  2. Pigeonhole Principle (Replies: 1)

Loading...