Euclid via Pigeonhole

Solution

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

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

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