- #1
karthikvs88
- 7
- 0
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: