[Verse 1]
Two numbers standing side by side
Which factor do they both divide?
The greatest common divisor's there
But finding it needs special care
Euclid knew the ancient way
Division steps that never stray
[Chorus]
Divide and take the remainder down
Pass it up, the old comes around
GCD of A and B
Becomes B mod repeatedly
Until the remainder hits zero clean
The last divisor's what we've seen
[Verse 2]
Two fifty-two and one oh five
Let's watch the algorithm come alive
Divide them out, forty-two remains
Now one oh five and forty-two chains
Forty-two goes into one oh five twice
Twenty-one's left, that's quite nice
[Chorus]
Divide and take the remainder down
Pass it up, the old comes around
GCD of A and B
Becomes B mod repeatedly
Until the remainder hits zero clean
The last divisor's what we've seen
[Bridge]
Forty-two and twenty-one now
Twenty-one divides exact somehow
Twenty-one and zero at the end
Twenty-one's the answer, my friend
Bézout says there's more to know
X and Y can make it flow
[Verse 3]
Extended algorithm finds the way
Integers X and Y at play
A times X plus B times Y
Equals GCD, that's no lie
Working backwards up the chain
Linear combinations we obtain
[Chorus]
Divide and take the remainder down
Pass it up, the old comes around
GCD of A and B
Becomes B mod repeatedly
Until the remainder hits zero clean
The last divisor's what we've seen
[Outro]
Three hundred BC, still running strong
O log of minimum, can't go wrong
Distillation pure and true
Common essence shining through