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 Bogomolny72009967