Formula for calculating the $α$ and $β$ in $\gcd(a, b) = αa + βb$

($\gcd$ stands for greatest common divisor)

So, I know when you calculate the greatest common divisor, the answer can be written as $\gcd(a, b) = αa + βb$ for some $α$ and $β$. My question is what a specific formula would be to calculate both of these values.

I was given $a_k = α_k · a + β_k · b$, where $a_0, a_1, \ldots$ is the sequence of values produced by the Euclidean Algorithm. I have to somehow use $a_{k+1} = α_{k+1} · a + β_{k+1} · b$ to work out formulas for $a_{k+1}$ and $β_{k+1}$ in terms of $k$ and $k - 1$. I can't figure out how to separate $a_{k+1}$ and $β_{k+1}$ to create two separate formulas, and after working through a problem using the Euclidean Algorithm I didn't see any patterns that would help me with this.

• What you're looking for is called the Extended Euclidean Algorithm. Interesting thing to note is that there are infinitely many values for $\alpha,\beta$ and they're given by $\alpha\equiv m\pmod{b}$ and $\beta\equiv n\pmod{a}$ where $(m,n)$ is any particular solution for $(\alpha,\beta)$ – learner Apr 12 '16 at 23:06
• Ah, my teacher just called it the Euclidean Algorithm. Is the only difference that the Extended Euclidean Algorithm calculates the greatest common divisor and states that it can be displayed as $gcd(a,b)=αa+βb$? – Chris Apr 12 '16 at 23:09
• The extended version is nothing but working backward through the equations found using the Euclidean Algorithm to calculate the $\gcd$. Working backward through the equations helps you get the solutions for the Bezout coefficients $\alpha,\beta$ – learner Apr 12 '16 at 23:12
• Here's an article showing an example on how to use the extended version to find those coefficients. – learner Apr 12 '16 at 23:13
• You can see a layout of the Extended Euclidean algorithm in action in an answer to [a question] (math.stackexchange.com/questions/1621690/…) on this site. – Bernard Apr 12 '16 at 23:16

3 Answers

I wish the explanation of the example had gone directly to the matrix description, which seems to me maximally transparent. When you start with $(a,b)$ you get a quotient and a remainder $r$ to form a new pair $(r,a)$ where $r=b-qa$. In matrix talk, $$\pmatrix{a\\r}=\pmatrix{0&1\\1&-q}\pmatrix{b\\a}\,.$$ If you try $\gcd(102,135)$, the matrices you get are, first $\pmatrix{0&1\\1&-1}$, then $\pmatrix{0&1\\1&-3}$, and finally $\pmatrix{0&1\\1&-11}$ to wind up with $\pmatrix{3\\0}$. Combining, \begin{align} \pmatrix{3\\0}&=\pmatrix{0&1\\1&-11}\pmatrix{0&1\\1&-3}\pmatrix{0&1\\1&-1}\pmatrix{135\\102}\\ &=\pmatrix{-3&4\\34&-45}\pmatrix{135\\102}\,. \end{align} And thus $3=\gcd(102,135)=-3\cdot135+4\cdot102$. If you multiply the matrices out right to left, you see that you actually get the $-3$ and $4$ as the bottom row of the next-to-last matrix, but no matter.

The upshot? Write down your quotients, make antidiagonal matrices with $0$ in the $(1,1)$ place and the sign-changed quotients in the $(2,2)$ place, put your matrices together in the right order, and multiply them out. And there you are.

But there is a simpler formula, but it uses euler's totient function. $$\varphi(n) =n \prod_{p\mid n} \left(1-\frac{1}{p}\right)$$

So if you can factor x or y, your task is done.

Say we have (a,b)=d, a=md b=nd, hence xmd+ynd=d, $$xm+yn=1\space and \space (m,n)=1$$ $$xm=1\mod y$$ $$x^{\phi(y)}=1 \mod y$$ $$m=x^{\phi(y)-1} \mod y$$ $$mx=1\mod y$$ $$mx=1+ky$$ $$k=\frac{mx-1}{y}$$

So you can use this formula: $$m=x^{\phi(y)-1} \mod y$$ $$k=\frac{mx-1}{y}$$ But you have to calculate $\phi(x)$ or exchange x for y and find $\phi(y)$.

Have a look at the extended Euclidean Algorithm.

You can try a live version at WolframAlpha entering "egcd(a,b)". This Example will return

{1, {-3, 2}}


which means $$\gcd(7,11) = 1 = (-3) \cdot 7 + 2 \cdot 11 = s \cdot a + t \cdot b$$

In this example the Bézout coefficients $s$, $t$ show up in the second last row of the $s_i$ and $t_i$ intermediate results.