Euclidean algorithm

Japanese school year: Math A

What you learn

You will learn an efficient algorithm to find the greatest common divisor of two integers using division remainders. It is especially useful when dealing with large numbers that are hard to factor. Familiarity with the division algorithm and properties of integer remainders is helpful before learning this.

Go to practice

Key points

This formula represents integer division. When an integer $a$ is divided by a positive integer $b$ , $q$ is the quotient and $r$ is the remainder, satisfying $0 \le r < b$ .

a = bq + r \quad (0 \le r < b)

Use this formula to efficiently find the GCD of large numbers. The GCD of $a$ and $b$ equals the GCD of the divisor $b$ and the remainder $r$ .

\gcd(a, b) = \gcd(b, r)

This equation shows that there exist integers $x$ and $y$ satisfying this relationship. You can find a specific solution pair $(x, y)$ by tracing the Euclidean algorithm backward.

ax + by = \gcd(a, b)

Choose a set to practice.

Practice 1Coming soon