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

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

• @saulspatz When I do $[4 \ 6 \ 9]\times C$ it gives $[1 \ 0 \ 0]$ so I do not see the mistake ... – Maman Apr 21 '18 at 15:39
• $C$ is not invertible though. I would guess that you multiplied a column by a scalar other than $\pm 1$. In the algorithm, you're allowed to add an arbitrary integer multiple of one column to another, but you're only allowed to multiply a column by $1$ or $-1$. – saulspatz Apr 21 '18 at 15:52
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$.