## Euclid via Pigeonhole

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

|Contact| |Front page| |Contents| |Up|

Copyright © 1996-2018 Alexander Bogomolny
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, ...,

### References

- A. Engel,
*Problem-Solving Strategies*, Springer Verlag, 1998, p. 61

|Contact| |Front page| |Contents| |Up|

Copyright © 1996-2018 Alexander Bogomolny66524378