GCD of 3 numbers, finding s, t, u

Question

I have to find the values s, u, t from GCD(88,99,111) = 88s + 99t + 111u

I know the GCD of this equation is 1 but I dont understand what it means by finding the values of s, t and u. Can someone please explain this to me.

Answer 1

Use the extended Euclidean algorithm to find the coefficients $u$ and $v$ of a Bézout's relation between $91$ and $143$:

\begin{array}{rrrc} r_i& u_i&v_i&q_i \\\hline 143 & 0 & 1 \\ 91 & 1 & 0 & 1 \\ \hline 52 & -1 & 1 & 1 \\ 39 & 2 &-1 & 1 \\ \hline 13 & \color{red}{-3} & \color{red}2 &3\\ 0 \end{array} Thus we have $\;-3\cdot 91+2\cdot 143=13$.

Now we need a Bézout's relation between $77$ and $13$. The extended Euclidean algorithm won't be necessary here, as there's an obvious solution: $\quad6\cdot 13 -77=1$.

Replacing $13$ with the first Bézout's relation, we obtain $$-77-18\cdot 91+12\cdot 143=1.$$