1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – dan_fulea Sep 2 '18 at 12:32
  • $\begingroup$ Use ${\rm GCD}(a,b,c) = {\rm GCD}(a,{\rm GCD}(b,c))$. Now apply the extended Euclidean alg. $\endgroup$ – Wuestenfux Sep 2 '18 at 12:35
  • $\begingroup$ 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? $\endgroup$ – Vincent Feb 1 at 8:34
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.