## Pigeon Hole Principle problem

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?
 PhysOrg.com science news on PhysOrg.com >> City-life changes blackbird personalities, study shows>> Origins of 'The Hoff' crab revealed (w/ Video)>> Older males make better fathers: Mature male beetles work harder, care less about female infidelity
 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.
 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.

## Pigeon Hole Principle problem

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.

 Tags modular arithmetic, number theory, relative prime

 Similar discussions for: Pigeon Hole Principle problem Thread Forum Replies Linear & Abstract Algebra 15 Set Theory, Logic, Probability, Statistics 9 Calculus & Beyond Homework 1 Introductory Physics Homework 4 General Math 10