✳flâneur — a map of the web's best reading

Extended Euclidean Algorithm - Algorithms for Competitive Programming

cp-algorithms.com · 1,014 words · saved by 1 readers

While the Euclidean algorithm calculates only the greatest common divisor (GCD) of two integers     𝑎 <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>a</mi></math> $a$  and     𝑏 <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>b</mi></math> $b$ , the extended version also finds a way to represent GCD in terms of     𝑎 <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>a</mi></math> $a$  and     𝑏 <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>b</mi></math> $b$ , i.e. coefficients     𝑥 <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>x</mi></math> $x$  and     𝑦 <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>y</mi></math> $y$  for which: It's important to note that by Bézout's identity we can always find such a representation. For instance,     gcd ( 55 , 80 ) = 5 <math xmlns="http://www.w3.org/1998/Math/MathML"><mo data-mjx-texclass="OP" movablelimits="true">gcd</mo><mo stretchy="false">(</mo><mn>55</mn><mo>,</mo><mn>80</mn><mo stretchy="false">)</mo>

Last update: January 19, 2026 &emsp; Translated From: e-maxx.ru Extended Euclidean Algorithm &para; While the Euclidean algorithm calculates only the greatest common divisor (GCD) of two non-negative integers $a$ and $b$ , the extended version also finds a way to represent GCD in terms of $a$ and $b$ , i.e. coefficients $x$ and $y$ for which: $$a \cdot x + b \cdot y = \gcd(a, b)$$ It's important to note that by Bézout's identity we can always find such a representation. For instance, $\gcd(55, 80) = 5$ , therefore we can represent $5$ as a linear combination with the terms $55$ and $80$ : $55

Explore this link on the map →

saved by

related reading