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| |Store|

Copyright © 1996-2017 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

Related material
Read more...

  • 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

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

    Copyright © 1996-2017 Alexander Bogomolny

     61190667

    Search by google: