Home › Math & Conversions › Core Math & Algebra › Euclidean algorithm Euclidean Algorithm Calculator Compute the greatest common divisor (GCD), view the division steps, and run the extended Euclidean algorithm with Bézout coefficients and modular inverses. Core Math & Algebra Interactive Euclidean algorithm tool Enter two integers and choose between the basic GCD computation and the extended Euclidean algorithm. The tool shows each division step and, in extended mode, the coefficients \(x\) and \(y\) such that \(\gcd(a,b) = a x + b y\). You can also optionally compute a modular inverse. Basic GCD & division steps Extended algorithm & modular inverse First integer \(a\) Nonzero integer (positive or negative). Second integer \(b\) Nonzero integer (positive or negative). Modulus \(m\) for inverse (optional) Used only in extended mode; requires \(\gcd(a, m) = 1\). Run algorithm Clear Load example: \(\gcd(252, 198)\) GCD result & division table – Input pair Greatest common divisor Number of divisions Division steps (Euclidean algorithm) Step Dividend Divisor Quotient Remainder Equation Interpretation Extended Euclidean algorithm – Input pair GCD Bézout identity Coefficient evolution The table shows how coefficients \((x_i, y_i)\) evolve so that each remainder \(r_i = a x_i + b y_i\). The last nonzero remainder is the GCD with its final coefficients. Step Quotient Remainder x y Modular inverse Interpretation What is the Euclidean algorithm? The Euclidean algorithm is a classical method to compute the greatest common divisor (GCD) of two integers \(a\) and \(b\). It is based on the key observation that \[ \gcd(a, b) = \gcd(b, r) \] whenever \(a = qb + r\) with \(0 \le r < |b|\). In other words, replacing the larger number by the remainder of the division does not change the greatest common divisor. Repeating this process eventually produces a remainder of 0; the last nonzero remainder is the GCD. Algorithm (division-based GCD) Starting from two integers \(a\) and \(b\), not both zero: Set \(a_0 = |a|\), \(b_0 = |b|\). While \(b_k \ne 0\), compute the quotient and remainder: \[ a_k = q_k b_k + r_k,\quad 0 \le r_k < b_k. \] Set \(a_{k+1} = b_k\), \(b_{k+1} = r_k\). When \(b_k = 0\), the GCD is \(a_k\). The table in the calculator shows the sequence of quotients \(q_k\) and remainders \(r_k\) until the algorithm terminates. The extended Euclidean algorithm The extended Euclidean algorithm doesn’t just give \(g = \gcd(a,b)\); it also finds integers \(x\) and \(y\) such that \[ g = \gcd(a,b) = a x + b y. \] These are called Bézout coefficients . They are crucial when you need a modular inverse: if \(\gcd(a, m) = 1\), then the coefficient \(x\) in \(1 = a x + m y\) gives a modular inverse of \(a \bmod m\) (specifically, \(a^{-1} \equiv x \pmod m\)). Applications of the Euclidean algorithm Reducing fractions to lowest terms (e.g., \( \frac{a}{b} = \frac{a/g}{b/g} \) where \(g = \gcd(a,b)\)). Solving linear Diophantine equations \(a x + b y = c\). Computing modular inverses in cryptographic protocols. Understanding the structure of integer lattices and continued fractions. Euclidean algorithm – FAQ Does the Euclidean algorithm always terminate? Yes. At each step, the remainder is strictly smaller than the divisor, so the sequence of nonnegative remainders decreases until it reaches 0. This guarantees termination in a finite number of steps. Why is the last nonzero remainder the GCD? Each remainder is a linear combination of the original integers \(a\) and \(b\), so it is divisible by any common divisor of \(a\) and \(b\). On the other hand, the last nonzero remainder divides the previous remainder and thus divides all preceding remainders and the original inputs. Together, these facts show that this last remainder is the greatest common divisor. What happens if one of the inputs is 0? By convention, \(\gcd(a, 0) = |a|\) and \(\gcd(0, b) = |b|\) for nonzero \(a\) and \(b\). The calculator enforces that at least one of the inputs is nonzero; if one is 0, the algorithm effectively stops after one step. Is the Euclidean algorithm only for integers? The classical algorithm is formulated for integers. Variants exist for polynomials over fields and for other Euclidean domains, but this calculator focuses on integers, which are the standard setting in elementary number theory and cryptography. How large can the numbers be? This implementation uses JavaScript’s safe integer range (roughly up to \(9 \times 10^{15}\) in absolute value). For very large integers used in industrial cryptographic libraries, you would typically rely on big-integer implementations of the Euclidean algorithm. Frequently Asked Questions What is the difference between the basic and extended Euclidean algorithm? The basic algorithm only tracks remainders and computes the greatest common divisor. The extended algorithm additionally tracks coefficients for the inputs a and b so that each remainder can be written as a linear combination of a and b. The last nonzero remainder provides the GCD and its Bézout coefficients. How do I use the tool to find a modular inverse? Switch to the extended mode, enter a as the integer whose inverse you want, and m as the modulus. If gcd(a, m) = 1, the calculator will report an x such that a · x ≡ 1 (mod m). If the GCD is not 1, no modular inverse exists with respect to m. Why does the calculator use absolute values internally? The GCD is always taken to be nonnegative, and gcd(a, b) = gcd(|a|, |b|). Using absolute values simplifies the division steps without changing the result, while signs are taken into account when reporting the Bézout coefficients. Related Core Math & Algebra tools Complement the Euclidean algorithm with these number theory and algebra calculators. Set theory Interval notation Base converter Exponent Fibonacci number Prime number Continued fraction Dice roll probability Pythagorean theorem SOHCAHTOA (trigonometry) Convolution All Math & Conversions tools Quick checklist Ensure at least one of \(a\), \(b\) is nonzero. Optionally simplify by dividing both numbers by small common factors. Run the Euclidean algorithm and confirm the last nonzero remainder. Use extended mode when you need Bézout coefficients or modular inverses. Document steps if you are presenting the computation in proofs or exams.

Subcategories in Home › Math & Conversions › Core Math & Algebra › Euclidean algorithm Euclidean Algorithm Calculator Compute the greatest common divisor (GCD), view the division steps, and run the extended Euclidean algorithm with Bézout coefficients and modular inverses. Core Math & Algebra Interactive Euclidean algorithm tool Enter two integers and choose between the basic GCD computation and the extended Euclidean algorithm. The tool shows each division step and, in extended mode, the coefficients \(x\) and \(y\) such that \(\gcd(a,b) = a x + b y\). You can also optionally compute a modular inverse. Basic GCD & division steps Extended algorithm & modular inverse First integer \(a\) Nonzero integer (positive or negative). Second integer \(b\) Nonzero integer (positive or negative). Modulus \(m\) for inverse (optional) Used only in extended mode; requires \(\gcd(a, m) = 1\). Run algorithm Clear Load example: \(\gcd(252, 198)\) GCD result & division table – Input pair Greatest common divisor Number of divisions Division steps (Euclidean algorithm) Step Dividend Divisor Quotient Remainder Equation Interpretation Extended Euclidean algorithm – Input pair GCD Bézout identity Coefficient evolution The table shows how coefficients \((x_i, y_i)\) evolve so that each remainder \(r_i = a x_i + b y_i\). The last nonzero remainder is the GCD with its final coefficients. Step Quotient Remainder x y Modular inverse Interpretation What is the Euclidean algorithm? The Euclidean algorithm is a classical method to compute the greatest common divisor (GCD) of two integers \(a\) and \(b\). It is based on the key observation that \[ \gcd(a, b) = \gcd(b, r) \] whenever \(a = qb + r\) with \(0 \le r < |b|\). In other words, replacing the larger number by the remainder of the division does not change the greatest common divisor. Repeating this process eventually produces a remainder of 0; the last nonzero remainder is the GCD. Algorithm (division-based GCD) Starting from two integers \(a\) and \(b\), not both zero: Set \(a_0 = |a|\), \(b_0 = |b|\). While \(b_k \ne 0\), compute the quotient and remainder: \[ a_k = q_k b_k + r_k,\quad 0 \le r_k < b_k. \] Set \(a_{k+1} = b_k\), \(b_{k+1} = r_k\). When \(b_k = 0\), the GCD is \(a_k\). The table in the calculator shows the sequence of quotients \(q_k\) and remainders \(r_k\) until the algorithm terminates. The extended Euclidean algorithm The extended Euclidean algorithm doesn’t just give \(g = \gcd(a,b)\); it also finds integers \(x\) and \(y\) such that \[ g = \gcd(a,b) = a x + b y. \] These are called Bézout coefficients . They are crucial when you need a modular inverse: if \(\gcd(a, m) = 1\), then the coefficient \(x\) in \(1 = a x + m y\) gives a modular inverse of \(a \bmod m\) (specifically, \(a^{-1} \equiv x \pmod m\)). Applications of the Euclidean algorithm Reducing fractions to lowest terms (e.g., \( \frac{a}{b} = \frac{a/g}{b/g} \) where \(g = \gcd(a,b)\)). Solving linear Diophantine equations \(a x + b y = c\). Computing modular inverses in cryptographic protocols. Understanding the structure of integer lattices and continued fractions. Euclidean algorithm – FAQ Does the Euclidean algorithm always terminate? Yes. At each step, the remainder is strictly smaller than the divisor, so the sequence of nonnegative remainders decreases until it reaches 0. This guarantees termination in a finite number of steps. Why is the last nonzero remainder the GCD? Each remainder is a linear combination of the original integers \(a\) and \(b\), so it is divisible by any common divisor of \(a\) and \(b\). On the other hand, the last nonzero remainder divides the previous remainder and thus divides all preceding remainders and the original inputs. Together, these facts show that this last remainder is the greatest common divisor. What happens if one of the inputs is 0? By convention, \(\gcd(a, 0) = |a|\) and \(\gcd(0, b) = |b|\) for nonzero \(a\) and \(b\). The calculator enforces that at least one of the inputs is nonzero; if one is 0, the algorithm effectively stops after one step. Is the Euclidean algorithm only for integers? The classical algorithm is formulated for integers. Variants exist for polynomials over fields and for other Euclidean domains, but this calculator focuses on integers, which are the standard setting in elementary number theory and cryptography. How large can the numbers be? This implementation uses JavaScript’s safe integer range (roughly up to \(9 \times 10^{15}\) in absolute value). For very large integers used in industrial cryptographic libraries, you would typically rely on big-integer implementations of the Euclidean algorithm. Frequently Asked Questions What is the difference between the basic and extended Euclidean algorithm? The basic algorithm only tracks remainders and computes the greatest common divisor. The extended algorithm additionally tracks coefficients for the inputs a and b so that each remainder can be written as a linear combination of a and b. The last nonzero remainder provides the GCD and its Bézout coefficients. How do I use the tool to find a modular inverse? Switch to the extended mode, enter a as the integer whose inverse you want, and m as the modulus. If gcd(a, m) = 1, the calculator will report an x such that a · x ≡ 1 (mod m). If the GCD is not 1, no modular inverse exists with respect to m. Why does the calculator use absolute values internally? The GCD is always taken to be nonnegative, and gcd(a, b) = gcd(|a|, |b|). Using absolute values simplifies the division steps without changing the result, while signs are taken into account when reporting the Bézout coefficients. Related Core Math & Algebra tools Complement the Euclidean algorithm with these number theory and algebra calculators. Set theory Interval notation Base converter Exponent Fibonacci number Prime number Continued fraction Dice roll probability Pythagorean theorem SOHCAHTOA (trigonometry) Convolution All Math & Conversions tools Quick checklist Ensure at least one of \(a\), \(b\) is nonzero. Optionally simplify by dividing both numbers by small common factors. Run the Euclidean algorithm and confirm the last nonzero remainder. Use extended mode when you need Bézout coefficients or modular inverses. Document steps if you are presenting the computation in proofs or exams..