## Euclid via Pigeonhole

For any two coprime intergers a, b there are two other integers x, y such that ax - by = 1.

Solution For any two coprime intergers a, b there are two other integers x, y such that ax - by = 1.

Elsewhere this fact has been proven by induction. Here we apply the Pigeonhole Principle.

Consider the remainders (mod b) of the b-term sequence a, 2a, ..., (b-1)a. The remainder 0 does not occur. In the absence of remainder 1, we would have pa = qa (mod b), for distinct p and q, 0 < q < p. This would imply that b divides (p - q)a, and since a and b are coprime, it divides p - q. But 0 < p, q < b. A contradiction. Therefore, there is x for which xa = 1 (mod b). In other words, ax = by + 1, for some y.

### References

1. A. Engel, Problem-Solving Strategies, Springer Verlag, 1998, p. 61 • Six integers out of 10: Pigeonhole Principle
• Pigeonhole Principle (Same sum)
• Pigeonhole in a Matrix
• Pigeonhole in Calendar
• A nice puzzle modeled on the Petersen graph
• Proizvolov's identity in a game format
• Pigeonhole with Disjoint Intervals
• All antichains
• Light Bulbs in a Circle (an Interactive Gizmo)
• Seven integers under 127 and their Ratios
• 