[Verse 1]
Two numbers standing side by side
The larger holds what they both hide
Divide and capture what remains
The algorithm breaks their chains
Replace the big with what's between
While smaller takes the bigger's scene
[Chorus]
GCD of a and b
Equals GCD of b, a mod b
Keep dividing, watch it shrink
Until remainder hits zero, think
Euclid's dance from ancient Greece
Strips away till factors cease
[Verse 2]
Start with forty-eight and eighteen
Forty-eight divided, what's the scene?
Two times eighteen leaves twelve behind
Now eighteen, twelve - the next you'll find
Eighteen equals twelve times one
Plus six remaining, not yet done
[Chorus]
GCD of a and b
Equals GCD of b, a mod b
Keep dividing, watch it shrink
Until remainder hits zero, think
Euclid's dance from ancient Greece
Strips away till factors cease
[Bridge]
Twelve and six, so six times two
Zero remainder, now we're through
The answer's six, the common thread
But there's more magic straight ahead
[Verse 3]
Extended version tells the tale
GCD equals ax plus by scale
Some integers x and y exist
Bézout's identity can't be missed
The greatest common factor's more
Than number - it's relationship's core
[Final Chorus]
GCD of a and b
Equals GCD of b, a mod b
Logarithmic steps to find
The essence that was intertwined
From modular math to Chinese rest
This ancient method proves the best
[Outro]
Two thousand years and counting strong
Euclid's algorithm marches on
Distillation, pure and clean
The greatest common in between