Let us compute the greatest common divisor of \(945\) and \(2415\text{.}\) First observe that
\begin{align*}
2415 & = 945 \cdot 2 + 525\\
945 & = 525 \cdot 1 + 420\\
525 & = 420 \cdot 1 + 105\\
420 & = 105 \cdot 4 + 0\text{.}
\end{align*}
Reversing our steps, 105 divides 420, 105 divides 525, 105 divides 945, and 105 divides 2415. Hence, 105 divides both 945 and 2415. If \(d\) were another common divisor of 945 and 2415, then \(d\) would also have to divide 105. Therefore, \(\gcd( 945, 2415 ) = 105\text{.}\)
If we work backward through the above sequence of equations, we can also obtain numbers \(r\) and \(s\) such that \(945 r + 2415 s = 105\text{.}\) Observe that
\begin{align*}
105 & = 525 + (-1) \cdot 420\\
& = 525 + (-1) \cdot [945 + (-1) \cdot 525]\\
& = 2 \cdot 525 + (-1) \cdot 945\\
& = 2 \cdot [2415 + (-2) \cdot 945] + (-1) \cdot 945\\
& = 2 \cdot 2415 + (-5) \cdot 945\text{.}
\end{align*}
So \(r = -5\) and \(s= 2\text{.}\) Notice that \(r\) and \(s\) are not unique, since \(r = 41\) and \(s = -16\) would also work.
To compute \(\gcd(a,b) = d\text{,}\) we are using repeated divisions to obtain a decreasing sequence of positive integers \(r_1 \gt r_2 \gt \cdots \gt r_n = d\text{;}\) that is,
\begin{align*}
b & = a q_1 + r_1\\
a & = r_1 q_2 + r_2\\
r_1 & = r_2 q_3 + r_3\\
& \vdots\\
r_{n - 2} & = r_{n - 1} q_{n} + r_{n}\\
r_{n - 1} & = r_n q_{n + 1}\text{.}
\end{align*}
To find \(r\) and \(s\) such that \(ar + bs = d\text{,}\) we begin with this last equation and substitute results obtained from the previous equations:
\begin{align*}
d & = r_n\\
& = r_{n - 2} - r_{n - 1} q_n\\
& = r_{n - 2} - q_n( r_{n - 3} - q_{n - 1} r_{n - 2} )\\
& = -q_n r_{n - 3} + ( 1+ q_n q_{n-1} ) r_{n - 2}\\
& \vdots\\
& = ra + sb\text{.}
\end{align*}