Euclidean algorithm, geometric interpretation, and the Stern-Brocot tree
GCD(,)
Press Compute to see the algorithm steps.
Rectangle×
GCD by filling a rectangle with squares.
Green: coprime pairs gcd(a,b)=1 · Blue shading: gcd > 1 · Probability of coprimality = 6/π² ≈ 60.8%
The Stern-Brocot tree contains every positive rational exactly once, in lowest terms.
About: The Euclidean algorithm (300 BCE) is one of the oldest algorithms still in use: gcd(a,b)=gcd(b, a mod b). Geometrically, it successively fills an a×b rectangle with the largest possible squares, with the final square size equal to gcd(a,b). The Stern-Brocot tree is a complete binary search tree containing every positive rational number exactly once in lowest terms — searching it for p/q takes gcd-many steps. The density of coprime pairs (gcd=1) in the integer lattice is 6/π² (Euler 1735, equivalent to ζ(2)=π²/6).