# GCD of 3 numbers, finding s, t, u

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.

• Just find $s,t,u\in\Bbb Z$ such that $77s+91t+143u=1$. First try to factor $77$, $91$, $143$. Then consider the above equation modulo seven. What can be said about $s,t,u$? – dan_fulea Sep 2 '18 at 12:32
• Use ${\rm GCD}(a,b,c) = {\rm GCD}(a,{\rm GCD}(b,c))$. Now apply the extended Euclidean alg. – Wuestenfux Sep 2 '18 at 12:35
• dan_fuela's comment and the answer below look quite surrealistic now with the 143, 91 and 77 coming out of nowhere. Did you change the numbers in the question? – Vincent Feb 1 at 8:34

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.$$