Pigeon Hole Principle problem

karthikvs88

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?

mathmadx

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.

karthikvs88

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.

karthikvs88

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.