• Support PF! Buy your school textbooks, materials and every day products Here!

Pigeon Hole Principle problem

  • #1

Homework Statement


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.


Homework Equations


none


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:

Answers and Replies

  • #2
17
0
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.
 
  • #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.
 
  • #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.
 

Related Threads on Pigeon Hole Principle problem

  • Last Post
Replies
3
Views
2K
Replies
14
Views
5K
Replies
1
Views
1K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
3
Views
3K
Replies
2
Views
2K
  • Last Post
Replies
6
Views
4K
  • Last Post
Replies
13
Views
977
  • Last Post
Replies
1
Views
3K
  • Last Post
Replies
5
Views
4K
Top