Find $x, y, z \in \mathbb{Z}$ such that :

Question

$4x+6y+9z=7$ using Smith's algorithm and linear system.

We can re-write the equation with : $[4 \ 6 \ 9]\times \left( \begin{array}{c} x\\ y\\ z \end{array}\right)=7$

I want to find a matrix $L \in \mathcal{GL}_1({\mathbb{Z}})$ ana a matrix $C\in \mathcal{GL}_3({\mathbb{Z}})$.

Here I found $C=\left( \begin{array}{c} -2 & 12 & 18 \\ 0 & 1 & 0 \\ 1 & -6 & -8 \end{array}\right) \notin \mathcal{GL}_3({\mathbb{Z}})$...

Moreover I know that I can take $L=1$.

How can I continue to solve this diophantine equation ?

Thanks in advance !

Answer 1

Here's how I did it. Starting with $$\pmatrix{4&6&9}$$ I subtracted the first column from the second, and $2$ times the first column from the third, resulting in $$\pmatrix{4&2&1}.$$ Then I interchanged the first and third columns, giving $$\pmatrix{1&2&4}.$$ After that, it's easy to reduce it to $$D=\pmatrix{1&0&0}.$$

Starting with a $3\times 3$ identity matrix, I did the same column operations, resulting in $$C=\pmatrix{-2&3&9\\0&1&0\\1&-2&-4},$$ which you can check has determinant $-1$.

Solving $DY=7$ gives $$Y=\pmatrix{7\\a\\b}$$ and $$\pmatrix{x\\y\\z}=CY\implies \pmatrix{x\\y\\z}=\pmatrix{-14+3a+9b\\a\\7-2a-4b}$$ as the solution, for arbitrary integers $a$ and $b$.