- #1

- 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: