The matrix Euclidean algorithm is reasonably useful to know, and reasonably easy to execute. The idea is to write down the remainders as a row vector on the right hand side of the equality. The left hand side will be a vector-matrix multiplication. To get the next line, on the right hand side we need to shift the right column one to the left, and then the new right column is a linear combination of the old columns. For instance 75 is one copy of 321 minus two copies of 123. The left hand side is done the same: the left column scoots over one to the left, and the right column is a linear combination. For instance $\begin{smallmatrix}1\\-2\end{smallmatrix}$ is one copy of the left column $\begin{smallmatrix}1\\0\end{smallmatrix}$ minus two copies of the right column $\begin{smallmatrix}0\\1\end{smallmatrix}$, abbreviated as $N=L-(2)(R)$.
So in each equation below, we figure out how to fix the right hand side using the division algorithm, then we just do the same thing to the left hand side.
$\newcommand{\matty}[6]{ \begin{bmatrix} 321 & 123 \end{bmatrix} \cdot \begin{bmatrix} #1 & #3 \\ #2 & #4 \end{bmatrix} = \begin{bmatrix} #5 & #6 \end{bmatrix}} \matty{1}{0}{0}{1}{321}{123} \phantom{ \qquad N = L - (2)(R) }\\ \matty{0}{1}{1}{-2}{123}{75} \qquad N = L - (2)(R) \\ \matty{1}{-2}{-1}{3}{75}{48} \qquad N = L - (1)(R)\\ \matty{-1}{3}{2}{-5}{48}{27} \qquad N = L - (1)(R)\\ \matty{2}{-5}{-3}{8}{27}{21} \qquad N = L - (1)(R)\\ \matty{-3}{8}{5}{-13}{21}{ 6} \qquad N = L - (1)(R)\\ \matty{5}{-13}{-18}{47}{ 6}{ 3} \qquad N = L - (3)(R)\\ \matty{-18}{47}{41}{-107}{ 3}{ 0} \qquad N = L - (2)(R)\\ $
This gives us the information that $3 = (321)(-18) + (123)(47)$ but even more, it tells us that $0 = (321)(41) + (123)(-107)$ so we can actually find lots of ways to get $3$:
$3 = (321)(-18+41k) + (123)(47-107k) \text{ for any } k$
so for instance we also get ($k=1$):
$3 = (321)(23) + (123)(-60)$