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.
 A: 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.
A: 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)$.
A: 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.
