Euclid via Pigeonhole

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

Solution


|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, ..., (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

[an error occurred while processing this directive]

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

Copyright © 1996-2018 Alexander Bogomolny
[an error occurred while processing this directive]
[an error occurred while processing this directive]