Extended Euclidean Examples

Number Theory · Axiom Academy

EXAMPLE Extended Euclidean Algorithm Finding integers x and y such that ax + by = gcd(a,b) Excellent work! You've completed this example of the Extended Euclidean Algorithm. Here's what we learned: Table Method: Organizing the Euclidean Algorithm in a table makes back-substitution much clearer and less error-prone. Back-Substitution Process: Work backwards from gcd(a,b), expressing each remainder in terms of a and b by substituting previous equations. Verification is Critical: Always check your answer by computing ax + by to ensure it equals gcd(a,b). Applications: This algorithm is fundamental for finding modular inverses in cryptography, solving linear Diophantine equations, and many other number theory applications. Sign Patterns: The coefficients x and y will have opposite signs when gcd(a,b) divides both a and b. Practice this method with different pairs of numbers. The table method works especially well for larger numbers where back-substitution can get complex!

This is the written version of the interactive lesson above. See the full Number Theory course.