Euclidean algorithm

In mathematics, the Euclidean algorithm, or Euclid's algorithm, is an efficient method for computing the greatest common divisor (GCD) of two integers, the largest number that divides them both without a remainder. It is named after the ancient Greek mathematician Euclid, who first described it in his Elements (c. 300 BC). It is an example of an algorithm, and is one of the oldest algorithms in common use. It can be used to reduce fractions to their simplest form, and is a part of many other number-theoretic and cryptographic calculations.

The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number. For example, 21 is the GCD of 252 and 105 (as 252 = 21 × 12 and 105 = 21 × 5), and the same number 21 is also the GCD of 105 and 252 − 105 = 147. Since this replacement reduces the larger of the two numbers, repeating this process gives successively smaller pairs of numbers until the two numbers become equal. When that occurs, that number is the GCD of the original two numbers. By reversing the steps or using the extended Euclidean algorithm, the GCD can be expressed as a linear combination of the two original numbers, that is the sum of the two numbers, each multiplied by an integer (for example, 21 = 5 × 105 + (−2) × 252). The fact that the GCD can always be expressed in this way is known as Bézout's identity.

The version of the Euclidean algorithm described above, which follows Euclid's original presentation, may require many subtraction steps to find the GCD when one of the given numbers is much bigger than the other. A more efficient version of the algorithm shortcuts these steps, instead replacing the larger of the two numbers by its remainder when divided by the smaller of the two (with this version, the algorithm stops when reaching a zero remainder). With this improvement, the algorithm never requires more steps than five times the number of digits (base 10) of the smaller integer. This was proven by Gabriel Lamé in 1844 (Lamé's Theorem), and marks the beginning of computational complexity theory. Additional methods for improving the algorithm's efficiency were developed in the 20th century.

The Euclidean algorithm has many theoretical and practical applications. It is used for reducing fractions to their simplest form and for performing division in modular arithmetic. Computations using this algorithm form part of the cryptographic protocols that are used to secure internet communications, and in methods for breaking these cryptosystems by factoring large composite numbers. The Euclidean algorithm may be used to solve Diophantine equations, such as finding numbers that satisfy multiple congruences according to the Chinese remainder theorem, to construct continued fractions, and to find accurate rational approximations to real numbers. Finally, it can be used as a basic tool for proving theorems in number theory such as Lagrange's four-square theorem and the uniqueness of prime factorizations.

Condensed: the full section is in Wikipedia.

The Euclidean algorithm calculates the greatest common divisor (GCD) of two natural numbers a and b. The greatest common divisor g is the largest natural number that divides both a and b without leaving a remainder. Synonyms for GCD include greatest common factor (GCF), highest common factor (HCF), highest common divisor (HCD), and greatest common measure (GCM). The greatest common divisor is often written as gcd(a, b) or, more simply, as (a, b), although the latter notation is ambiguous, also used for concepts such as an ideal in the ring of integers, which is closely related to GCD.

If gcd(a, b) = 1, then a and b are said to be coprime (or relatively prime). This property does not imply that a or b are themselves prime numbers. For example, 6 and 35 factor as 6 = 2 × 3 and 35 = 5 × 7, so they are not prime, but their prime factors are different, so 6 and 35 are coprime, with no common factors other than 1.

Let g = gcd(a, b). Since a and b are both multiples of g, they can be written a = mg and b = ng, and there is no larger number G > g for which this is true. The natural numbers m and n must be coprime, since any common factor could be factored out of m and n to make g greater. Thus, any other number c that divides both a and b must also divide g. The greatest common divisor g of a and b is the unique (positive) common divisor of a and b that is divisible by any other common divisor c.

The greatest common divisor can be visualized as follows. Consider a rectangular area a by b, and any common divisor c that divides both a and b exactly. The sides of the rectangle can be divided into segments of length c, which divides the rectangle into a grid of squares of side length c. The GCD g is the largest value of c for which this is possible. For illustration, a 24×60 rectangular area can be divided into a grid of: 1×1 squares, 2×2 squares, 3×3 squares, 4×4 squares, 6×6 squares or 12×12 squares. Therefore, 12 is the GCD of 24 and 60. A 24×60 rectangular area can be divided into a grid of 12×12 squares, with two squares along one edge (24/12 = 2) and five squares along the other (60/12 = 5).

The greatest common divisor of two numbers a and b is the product of the prime factors shared by the two numbers, where each prime factor can be repeated as many times as it divides both a and b. For example, since 1386 can be factored into 2 × 3 × 3 × 7 × 11, and 3213 can be factored into 3 × 3 × 3 × 7 × 17, the GCD of 1386 and 3213 equals 63 = 3 × 3 × 7, the product of their shared prime factors (with 3 repeated since 3 × 3 divides both). If two numbers have no common prime factors, their GCD is 1 (obtained here as an instance of the empty product); in other words, they are coprime. A key advantage of the Euclidean algorithm is that it can find the GCD efficiently without having to compute the prime factors. Factorization of large integers is believed to be a computationally very difficult problem, and the security of many widely used cryptographic protocols is based upon its infeasibility.

gcd(a, b, c) = gcd(a, gcd(b, c)) = gcd(gcd(a, b), c) = gcd(gcd(a, c), b).

Condensed: the full section is in Wikipedia.

a = 1071; b = 462

Restart Start

The Euclidean algorithm can be thought of as constructing a sequence of non-negative integers that begins with the two given integers \(r_{-2} = a\) and \(r_{-1} = b\) and will eventually terminate with the integer zero: \(\{ r_{-2} = a,\ r_{-1} = b,\ r_0,\ r_1,\ \cdots,\ r_{n-1},\ r_n = 0 \}\) with \(r_{k+1} < r_k.\) The integer \(r_{n-1}\) will then be the GCD and we can state \(\text{gcd}(a,b) = r_{n-1}.\) The algorithm indicates how to construct the intermediate remainders \(r_k\) via division-with-remainder on the preceding pair \((r_{k-2},\ r_{k-1})\) by finding an integer quotient \(q_k\) so that:

\(r_{k-2} = q_k \cdot r_{k-1} + r_k \text{, with } \ r_{k-1} > r_k \geq 0.\)

Because the sequence of non-negative integers \(\{ r_k \}\) is strictly decreasing, it eventually must terminate. In other words, since \(r_k \ge 0\) for every \(k,\) and each \(r_k\) is an integer that is strictly smaller than the preceding \(r_{k-1},\) there eventually cannot be a non-negative integer smaller than zero, and hence the algorithm must terminate. In fact, the algorithm will always terminate at the nth step with \(r_n\) equal to zero.

To illustrate, suppose the GCD of 1071 and 462 is requested. The sequence is initially \(\{r_{-2} = 1071,\ r_{-1} = 462 \}\) and in order to find \(r_0,\) we need to find integers \(q_0\) and \(r_0 < r_{-1}\) such that:

\(1071 = q_0 \cdot 462 + r_0.\)

This is the quotient \(q_0 = 2\) since \(1071 = 2 \cdot 462 + 147.\) This determines \(r_0 = 147\) and so the sequence is now \(\{1071,\ 462,\ r_0 = 147 \}.\) The next step is to continue the sequence to find \(r_1\) by finding integers \(q_1\) and \(r_1 < r_0\) such that:

\(462 = q_1 \cdot 147 + r_1.\)

This is the quotient \(q_1 = 3\) since \(462 = 3 \cdot 147 + 21.\) This determines \(r_1 = 21\) and so the sequence is now \(\{1071,\ 462,\ 147,\ r_1 = 21 \}.\) The next step is to continue the sequence to find \(r_2\) by finding integers \(q_2\) and \(r_2 < r_1\) such that:

\(147 = q_2 \cdot 21 + r_2.\)

This is the quotient \(q_2 = 7\) since \(147 = 7 \cdot 21 + 0.\) This determines \(r_2 = 0\) and so the sequence is completed as \(\{1071,\ 462,\ 147,\ 21,\ r_2 = 0 \}\) as no further non-negative integer smaller than \(0\) can be found. The penultimate remainder \(21\) is therefore the requested GCD:

\(\text{gcd}(1071,\ 462) = 21.\)

We can generalize slightly by dropping any ordering requirement on the initial two values \(a\) and \(b.\) If \(a = b,\) the algorithm may continue and trivially find that \(\text{gcd}(a,\ a) = a\) as the sequence of remainders will be \(\{a,\ a,\ 0\}.\) If \(a < b,\) then we can also continue since \(a \equiv 0 \cdot b + a,\) suggesting the next remainder should be \(a\) itself, and the sequence is \(\{a,\ b,\ a,\ \cdots \}.\) Normally, this would be invalid because it breaks the requirement \(r_0 < r_{-1}\) but now we have \(a < b\) by construction, so the requirement is automatically satisfied and the Euclidean algorithm can continue as normal. Therefore, dropping any ordering between the first two integers does not affect the conclusion that the sequence must eventually terminate because the next remainder will always satisfy \(r_0 < b\) and everything continues as above. The only modifications that need to be made are that \(r_{k} < r_{k-1}\) only for \(k \ge 0,\) and that the sub-sequence of non-negative integers \(\{ r_{k-1} \}\) for \(k \ge 0\) is strictly decreasing, therefore excluding \(a = r_{-2}\) from both statements.

The existence of a step \(N\) such that \(r_N=0\) follows from the condition \(|r_i|<|r_{i-1}|\), for \(i\geq1\). This ensures that the algorithm terminates.

The last non-zero remainder \(r_{N-1}\) being equal to \(\gcd(a,b)\) follows from the following properties of \(\gcd\)

1. \(\gcd(x,0)=x\), for all \(x\neq0\).

In fact, the common divisors of \(x\) and \(0\) are exactly all the divisors of \(x\), of which \(x\) itself is the largest.

2. \(\gcd(x,y)=\gcd(y,x-zy)\)

In fact, the sets of common divisors of the pairs \((x,y)\) and \((y, x-zy)\) are the same. In particular, the largest of their common divisors are the same.

To see this, assume that \(d\) is a common divisor of \(x\) and \(y\). This means that there are integers \(X,Y\) such that \(x=dX\) and \(y=dY\). It follows that \(x-zy=dX-zdY=d(X-zY)\), where \(X-zY\) is an integer. Therefore, \(d\) is also a divisor of \(x-zy\).

Conversely, if \(d\) is a common divisor of \(x-zy\) and \(y\), then there are integers \(Z\) and \(Y\) such that \(x-zy=dZ\) and \(y=dY\). From this \(x=(x-zy)+zy=dZ+zdY=d(Z+zY)\), where \(Z+zY\) is an integer. Therefore, \(d\) is also a common divisor of \(x\) and \(y\).

Now, the Euclidean algorithm starts with the pair \((r_{-2},r_{-1})=(a,b)\) and at each step, the pair of remainders \((r_{k-2},r_{k-1})\) is replaced by \((r_{k-1},r_{k-2}-q_kr_{k-1})=(r_{k-1},r_{k})\). Property 2 shows that the \(\gcd\) of the pairs remains invariant. In particular, the \(\gcd\) of the first pair \((a,b)\) and the last pair \((r_{N-1},0)\) are the same. Applying Property 1, \(\gcd(a,b)=\gcd(r_{N-1},0)=r_{N-1}\).

For illustration, the Euclidean algorithm can be used to find the greatest common divisor of a = 1071 and b = 462. To begin, multiples of 462 are subtracted from 1071 until the remainder is less than 462. Two such multiples can be subtracted (q₀ = 2), leaving a remainder of 147:

1071 = 2 × 462 + 147.

Then multiples of 147 are subtracted from 462 until the remainder is less than 147. Three multiples can be subtracted (q₁ = 3), leaving a remainder of 21:

462 = 3 × 147 + 21.

Then multiples of 21 are subtracted from 147 until the remainder is less than 21. Seven multiples can be subtracted (q₂ = 7), leaving no remainder:

147 = 7 × 21 + 0.

Since the last remainder is zero, the algorithm ends with 21 as the greatest common divisor of 1071 and 462. This agrees with the gcd(1071, 462) found by prime factorization above. In tabular form, the steps are:

The Euclidean algorithm can be visualized in terms of the tiling analogy given above for the greatest common divisor. Assume that we wish to cover an a×b rectangle with square tiles exactly, where a is the larger of the two numbers. We first attempt to tile the rectangle using b×b square tiles; however, this leaves an r₀×b residual rectangle untiled, where r₀ < b. We then attempt to tile the residual rectangle with r₀×r₀ square tiles. This leaves a second residual rectangle r₁×r₀, which we attempt to tile using r₁×r₁ square tiles, and so on. The sequence ends when there is no residual rectangle, i.e., when the square tiles cover the previous residual rectangle exactly. The length of the sides of the smallest square tile is the GCD of the dimensions of the original rectangle. For example, the smallest square tile in the adjacent figure is 21×21 (shown in red), and 21 is the GCD of 1071 and 462, the dimensions of the original rectangle (shown in green).

At every step k, the Euclidean algorithm computes a quotient q_k and remainder r_k from two numbers r_k−1 and r_k−2

r_k−2 = q_k r_k−1 + r_k,

where the r_k is non-negative and is strictly less than the absolute value of r_k−1. The theorem which underlies the definition of the Euclidean division ensures that such a quotient and remainder always exist and are unique.

In Euclid's original version of the algorithm, the quotient and remainder are found by repeated subtraction; that is, r_k−1 is subtracted from r_k−2 repeatedly until the remainder r_k is smaller than r_k−1. After that r_k and r_k−1 are exchanged and the process is iterated. Euclidean division reduces all the steps between two exchanges into a single step, which is thus more efficient. Moreover, the quotients are not needed, thus one may replace Euclidean division by the modulo operation, which gives only the remainder. Thus the iteration of the Euclidean algorithm becomes simply

r_k = r_k−2 mod r_k−1.

Implementations of the algorithm may be expressed in pseudocode. For example, the division-based version may be programmed as

At the beginning of the kth iteration, the variable b holds the latest remainder r_k−1, whereas the variable a holds its predecessor, r_k−2. The step b := a mod b is equivalent to the above recursion formula r_k ≡ r_k−2 mod r_k−1. The temporary variable t holds the value of r_k−1 while the next remainder r_k is being calculated. At the end of the loop iteration, the variable b holds the remainder r_k, whereas the variable a holds its predecessor, r_k−1.

(If negative inputs are allowed, or if the mod function may return negative values, the last line must be replaced with return abs(a).)

In the subtraction-based version, which was Euclid's original version, the remainder calculation (b := a mod b) is replaced by repeated subtraction. Contrary to the division-based version, which works with arbitrary integers as input, the subtraction-based version supposes that the input consists of positive integers and stops when a = b:

The variables a and b alternate holding the previous remainders r_k−1 and r_k−2. Assume that a is larger than b at the beginning of an iteration; then a equals r_k−2, since r_k−2 > r_k−1. During the loop iteration, a is reduced by multiples of the previous remainder b until a is smaller than b. Then a is the next remainder r_k. Then b is reduced by multiples of a until it is again smaller than a, giving the next remainder r_k+1, and so on.

The recursive version is based on the equality of the GCDs of successive remainders and the stopping condition gcd(r_N−1, 0) = r_N−1.

(As above, if negative inputs are allowed, or if the mod function may return negative values, the instruction return a must be replaced by return max(a, −a).)

Condensed: the full section is in Wikipedia.

In another version of Euclid's algorithm, the quotient at each step is increased by one if the resulting negative remainder is smaller in magnitude than the typical positive remainder. Previously, the equation

r_k−2 = q_k r_k−1 + r_k

assumed that |r_k−1| > r_k > 0. However, an alternative negative remainder e_k can be computed:

r_k−2 = (q_k + 1) r_k−1 + e_k

if r_k−1 > 0 or

r_k−2 = (q_k, 1) r_k−1 + e_k

if r_k−1 < 0.

If r_k is replaced by e_k. when |e_k| < |r_k|, then one gets a variant of Euclidean algorithm such that

|r_k| ≤ |r_k−1| / 2

at each step.

Leopold Kronecker has shown that this version requires the fewest steps of any version of Euclid's algorithm. More generally, it has been proven that, for every input numbers a and b, the number of steps is minimal if and only if q_k is chosen in order that \(\left |\frac{r_{k+1}}{r_k}\right |<\frac{1}{\varphi}\sim 0.618,\) where \(\varphi\) is the golden ratio.

The Euclidean algorithm is one of the oldest algorithms in common use. It appears in Euclid's Elements (c. 300 BC), specifically in Book 7 (Propositions 1-2) and Book 10 (Propositions 2-3). In Book 7, the algorithm is formulated for integers, whereas in Book 10, it is formulated for lengths of line segments. (In modern usage, one would say it was formulated there for real numbers. But lengths, areas, and volumes, represented as real numbers in modern usage, are not measured in the same units and there is no natural unit of length, area, or volume; the concept of real numbers was unknown at that time.) The latter algorithm is geometrical. The GCD of two lengths a and b corresponds to the greatest length g that measures a and b evenly; in other words, the lengths a and b are both integer multiples of the length g.

The algorithm was probably not discovered by Euclid, who compiled results from earlier mathematicians in his Elements. The mathematician and historian B. L. van der Waerden suggests that Book VII derives from a textbook on number theory written by mathematicians in the school of Pythagoras. The algorithm was probably known by Eudoxus of Cnidus (about 375 BC). The algorithm may even pre-date Eudoxus, judging from the use of the technical term ἀνθυφαίρεσις (anthyphairesis, reciprocal subtraction) in works by Euclid and Aristotle. Claude Brezinski, following remarks by Pappus of Alexandria, credits the algorithm to Theaetetus (c. 417, c. 369 BC).

Centuries later, Euclid's algorithm was discovered independently both in India and in China, primarily to solve Diophantine equations that arose in astronomy and making accurate calendars. In the late 5th century, the Indian mathematician and astronomer Aryabhata described the algorithm as the "pulverizer", perhaps because of its effectiveness in solving Diophantine equations. Although a special case of the Chinese remainder theorem had already been described in the Chinese book Sunzi Suanjing, the general solution was published by Qin Jiushao in his 1247 book Shushu Jiuzhang (數書九章 Mathematical Treatise in Nine Sections). The Euclidean algorithm was first described numerically and popularized in Europe in the second edition of Bachet's Problèmes plaisants et délectables (Pleasant and enjoyable problems, 1624). In Europe, it was likewise used to solve Diophantine equations and in developing continued fractions. The extended Euclidean algorithm was published by the English mathematician Nicholas Saunderson, who attributed it to Roger Cotes as a method for computing continued fractions efficiently.

Other applications of Euclid's algorithm were developed in the 19th century. In 1829, Charles Sturm showed that the algorithm was useful in the Sturm chain method for counting the real roots of polynomials in any given interval.

Condensed: the full section is in Wikipedia.

Bézout's identity states that the greatest common divisor g of two integers a and b can be represented as a linear sum of the original two numbers a and b. In other words, it is always possible to find integers s and t such that g = sa + tb.

The integers s and t can be calculated from the quotients q₀, q₁, etc. by reversing the order of equations in Euclid's algorithm. Beginning with the next-to-last equation, g can be expressed in terms of the quotient q_N−1 and the two preceding remainders, r_N−2 and r_N−3:

g = r_N−1 = r_N−3 − q_N−1 r_N−2.

Those two remainders can be likewise expressed in terms of their quotients and preceding remainders,

r_N−2 = r_N−4 − q_N−2 r_N−3 and

r_N−3 = r_N−5 − q_N−3 r_N−4.

Substituting these formulae for r_N−2 and r_N−3 into the first equation yields g as a linear sum of the remainders r_N−4 and r_N−5. The process of substituting remainders by formulae involving their predecessors can be continued until the original numbers a and b are reached:

r₂ = r₀ − q₂ r₁

r₁ = b − q₁ r₀

r₀ = a − q₀ b.

After all the remainders r₀, r₁, etc. have been substituted, the final equation expresses g as a linear sum of a and b, so that g = sa + tb.

The Euclidean algorithm, and thus Bézout's identity, can be generalized to the context of Euclidean domains.

Bézout's identity provides yet another definition of the greatest common divisor g of two numbers a and b. Consider the set of all numbers ua + vb, where u and v are any two integers. Since a and b are both divisible by g, every number in the set is divisible by g. In other words, every number of the set is an integer multiple of g. This is true for every common divisor of a and b. However, unlike other common divisors, the greatest common divisor is a member of the set; by Bézout's identity, choosing u = s and v = t gives g. A smaller common divisor cannot be a member of the set, since every member of the set must be divisible by g. Conversely, any multiple m of g can be obtained by choosing u = ms and v = mt, where s and t are the integers of Bézout's identity. This may be seen by multiplying Bézout's identity by m,

mg = msa + mtb.

Therefore, the set of all numbers ua + vb is equivalent to the set of multiples m of g. In other words, the set of all possible sums of integer multiples of two numbers (a and b) is equivalent to the set of multiples of gcd(a, b). The GCD is said to be the generator of the ideal of a and b. This GCD definition led to the modern abstract algebraic concepts of a principal ideal (an ideal generated by a single element) and a principal ideal domain (a domain in which every ideal is a principal ideal).

Certain problems can be solved using this result. For example, consider two measuring cups of volume a and b. By adding/subtracting u multiples of the first cup and v multiples of the second cup, any volume ua + vb can be measured out. These volumes are all multiples of g = gcd(a, b).

The integers s and t of Bézout's identity can be computed efficiently using the extended Euclidean algorithm. This extension adds two recursive equations to Euclid's algorithm

s_k = s_k−2 − q_ks_k−1

t_k = t_k−2 − q_kt_k−1

with the starting values

s₋₂ = 1, t₋₂ = 0

s₋₁ = 0, t₋₁ = 1.

Using this recursion, Bézout's integers s and t are given by s = s_N and t = t_N, where N + 1 is the step on which the algorithm terminates with r_N+1 = 0.

The validity of this approach can be shown by induction. Assume that the recursion formula is correct up to step k − 1 of the algorithm; in other words, assume that

r_j = s_j a + t_j b

for all j less than k. The kth step of the algorithm gives the equation

r_k = r_k−2 − q_kr_k−1.

Since the recursion formula has been assumed to be correct for r_k−2 and r_k−1, they may be expressed in terms of the corresponding s and t variables

r_k = (s_k−2 a + t_k−2 b) − q_k(s_k−1 a + t_k−1 b).

Rearranging this equation yields the recursion formula for step k, as required

r_k = s_k a + t_k b = (s_k−2 − q_ks_k−1) a + (t_k−2 − q_kt_k−1) b.

The integers s and t can also be found using an equivalent matrix method. The sequence of equations of Euclid's algorithm

\(\begin{align} a & = q_0 b + r_0 \\ b & = q_1 r_0 + r_1 \\ & \,\,\,\vdots \\ r_{N-2} & = q_N r_{N-1} + 0 \end{align}\)

can be written as a product of 2×2 quotient matrices multiplying a two-dimensional remainder vector

\(\begin{pmatrix} a \\ b \end{pmatrix} = \begin{pmatrix} q_0 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} b \\ r_0 \end{pmatrix} = \begin{pmatrix} q_0 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} q_1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} r_0 \\ r_1 \end{pmatrix} = \cdots = \prod_{i=0}^N \begin{pmatrix} q_i & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} r_{N-1} \\ 0 \end{pmatrix} \,.\)

Let M represent the product of all the quotient matrices

\(\mathbf{M} = \begin{pmatrix} m_{11} & m_{12} \\ m_{21} & m_{22} \end{pmatrix} = \prod_{i=0}^N \begin{pmatrix} q_i & 1 \\ 1 & 0 \end{pmatrix} = \begin{pmatrix} q_0 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} q_1 & 1 \\ 1 & 0 \end{pmatrix} \cdots \begin{pmatrix} q_{N} & 1 \\ 1 & 0 \end{pmatrix} \,.\)

This simplifies the Euclidean algorithm to the form

\(\begin{pmatrix} a \\ b \end{pmatrix} = \mathbf{M} \begin{pmatrix} r_{N-1} \\ 0 \end{pmatrix} = \mathbf{M} \begin{pmatrix} g \\ 0 \end{pmatrix} \,.\)

To express g as a linear sum of a and b, both sides of this equation can be multiplied by the inverse of the matrix M. The determinant of M equals (−1), since it equals the product of the determinants of the quotient matrices, each of which is negative one. Since the determinant of M is never zero, the vector of the final remainders can be solved using the inverse of M

\(\begin{pmatrix} g \\ 0 \end{pmatrix} = \mathbf{M}^{-1} \begin{pmatrix} a \\ b \end{pmatrix} = (-1)^{N+1} \begin{pmatrix} m_{22} & -m_{12} \\ -m_{21} & m_{11} \end{pmatrix} \begin{pmatrix} a \\ b \end{pmatrix} \,.\)

Since the top equation gives

g = (−1) ( m₂₂ a − m₁₂ b),

the two integers of Bézout's identity are s = (−1)m₂₂ and t = (−1)m₁₂. The matrix method is as efficient as the equivalent recursion, with two multiplications and two additions per step of the Euclidean algorithm.