The question says:
- Find a and b integers where:
$671a-654b = 18$ and $\gcd(a,b) = 18$
My attempt was:
$a = cd$ where $d$ is $\gcd$ and $c$ is just an integer.
$b = kd$ where $k$ is just an integer too.
$k$ and $c$ are co-prime, btw (This is all according to a law in math, I don't know its name though)
By putting them in the equation we find:
$d(671c - 654k) = 18$
which is
$671c - 654k = 1$
By using the euclidean algorithm, I only found this which is not correct:
$76(671) - 78(654) = -16$
-$16$ should be $1$ in its place but it isn't, so it's not right, either.
So how do I continue from here?
EDIT: I redid my algorithm and I found that $c = 77$ and $k = -79$ which after putting it in a and b, I find their values. Thank you all!
Hint:
Use first the extended Euclidean algorithm to find $u$ and $v$ such that $$671u-654v=1$$ since $671$ and $654$ are coprime, then multiply $u$ and $v$ by $18$ to obtain $a$ and $b$.
Added. The algorithm:
\begin{array}{rrrl} r_k & u_k & v_k & q_k \\ \hline 671 & 1 & 0 \\ 654 & 0 & 1 & 1 \\ \hline 17 & 1 & -1 & 38 \\ 8 & -38 & 39 & 2 \\ 1 & \color{red}{77} & \color{red}{-79} \\ \hline \end{array}