[Verse 1]
Euclidean algorithm finds the greatest common divisor
But what if we need coefficients? Time to get wiser
Extended version tracks the linear combination
Bezout's identity through computational creation
Start with two integers, call them a and b
We'll find the GCD plus x and y that decree
a times x plus b times y equals that GCD
Backward substitution reveals the mystery
[Chorus]
Divide and conquer, track the quotients down
Remainder zero means the GCD is found
But save those steps, we're working backwards now
Express each remainder, show me exactly how
Extended Euclidean, coefficients revealed
Linear combination, mathematically sealed
[Verse 2]
Initialize the table, six columns in a row
r s t q old new, watch the pattern flow
r-old starts with a, r-new begins with b
s-old equals one, s-new is zero, see
t-old equals zero, t-new is one to start
Division algorithm tears remainders apart
While r-new isn't zero, keep the cycle spinning
Update all the values, fresh iteration beginning
[Chorus]
Divide and conquer, track the quotients down
Remainder zero means the GCD is found
But save those steps, we're working backwards now
Express each remainder, show me exactly how
Extended Euclidean, coefficients revealed
Linear combination, mathematically sealed
[Bridge]
Quotient equals r-old divided by r-new
Temp variables hold what we're about to do
r-old becomes r-new, r-new gets the remainder
s and t update with the same container
s-new equals s-old minus quotient times s-new
t follows the pattern, algebraic breakthrough
[Verse 3]
When r-new hits zero, the algorithm halts
r-old holds the GCD, despite any faults
s-old and t-old are the coefficients we seek
Bezout's equation, elegant and sleek
Cryptography needs this, modular inverse found
RSA encryption, mathematically sound
Diophantine equations bow to this technique
Extended Euclidean makes solutions unique
[Outro]
From ancient Greece to modern computation
Extended algorithm, mathematical foundation
Remember the invariant through every iteration
Linear combination, perfect preservation