# Find all the integral solutions to the equation $323x+391y+437z=10473$

Find all the integral solutions to the equation $$323x+391y+437z=10473$$.

I know how to find integer solutions in two variables using Diophantine Equations.

But I am stuck here because it involves 3 variables.

Can I get a hint?

• It might be helpful to factor each of the coefficients in this one. They set up a nice set of relations that you can then solve. – Kitter Catter Aug 16 at 15:20
• From your original question is sounds like you are completely stuck. Please show all the work you have, and what techniques/what you want explained in the answers so that others can better answer your question. – Toby Mak Aug 17 at 5:49
• Your question just asks for a hint. That's fine, but your comments on some of the answers below seem to suggest that you are not satisfied with hints and are looking for a full answer. This is a little inconsiderate of those who have taken the trouble to try to respond to your question. Please try to formulate questions so that they make clear exactly what you are looking for (and as Toby Mak says include your own thoughts / work). – Adam Bailey Aug 17 at 10:40
• I added a proof of the general formula cited in Robert's answer, and also added an answer using (Hermite) row reduction for comparison. – Bill Dubuque Aug 18 at 17:01

Since $$\gcd(323,391,437)=1$$ divide $$10473$$ we are supposed to find infinite solutions.

Hint. First find a solution $$u_0$$, $$v_0$$ of $$19u + 23 v = 437$$ where $$19=323/17$$ and $$23=391/17$$ with $$17=\gcd(323,391)$$. Then let $$t_0$$, $$z_0$$ be a solution of $$17t+ 437z=10473$$ and $$x_0$$, $$y_0$$ be a solution of $$19x + 23y = t_0.$$ Then $$(x_0,y_0,z_0)$$ is a particular solution of $$323x+391y+437z=10473$$, whereas the general solution is given by $$\begin{cases} x = x_0 - 23k - u_0j\\ y = y_0 + 19k - v_0j\\ z = z_0 + 17j \end{cases}$$ with $$j,k\in\mathbb{Z}$$.

Then compare your result given by Script.

P.S. Finally, I got the general solution: $$\begin{cases} x = 8 - 23k -23j\\ y = 9 + 19k\\ z = 10 + 17j \end{cases}\tag{*}$$ with $$j,k\in\mathbb{Z}$$.

Verification that (*) are ALL the solutions of the given linear Diophantine equation. It is easy to check that the particular solution $$(x_0,y_0,z_0)=(8,9,10)$$ works. Moreover, the related homogeneous equation is $$323(x-x_0)+391(y-y_0)+437(z-z_0)\\=17\cdot 19 (x-x_0)+17\cdot 23(y-y_0)+19\cdot 23 (z-z_0)=0$$ and it follows that $$z-z_0$$ is a multiple of $$17$$, i.e. $$z = z_0 + 17j$$, $$y-y_0$$ is a multiple of $$19$$, i.e. $$y = y_0 + 19k$$, and therefore $$x=x_0-\frac{391(y-y_0)+437(z-z_0)}{323}=x_0-\frac{(17\cdot 19)\cdot 23 k+(19\cdot 23) \cdot 17j}{17\cdot 19}\\=x_0-23k-23j$$ and we are done.

Note that along the same lines, you may show that the method outlined above works in general.

• I did that exactly – Math_Freak Aug 16 at 15:07
• on solving the first equation i got (1885140+437t,-73311-437t) – Math_Freak Aug 16 at 15:08
• But how to complete – Math_Freak Aug 16 at 15:08
• i dont get it, can u help me to complete my solution – Math_Freak Aug 16 at 15:12
• how to arrive to solution from this solution $(1885140+437t,-73311-437t)$ – Math_Freak Aug 16 at 15:13

Hint. To mod $$17$$, $$323\equiv0$$, $$391\equiv0$$, $$437\equiv12$$ and $$10473\equiv1$$. Hence $$z$$ must be such that $$12z\equiv1\pmod{17}$$. Similar constraints can be found on $$x$$ using mod $$23$$ and $$y$$ using mod $$19$$.

• and all of them need to be odd based on parity, or exactly 1 of them. – Roddy MacPhee Aug 16 at 18:40

Applying the Extended Euclidean Algorithm

The Extended Euclidean Algorithm is usually applied to a pair of numbers, but by combining the results from the pairs $$(391,323)$$, $$(437,391)$$, and $$(437,323)$$, we can get a similar result for the triple $$(437,391,323)$$.

Applying the Extended Euclidean Algorithm as implemented in this answer to $$391$$ and $$323$$ $$\begin{array}{r} &&1&4&1&3\\\hline 1&0&1&-4&5&-19\\ 0&1&-1&5&-6&23\\ 391&323&68&51&17&0\\ \end{array}$$ we get $$\gcd(391,323)=17$$ and \begin{align} 5\cdot391-6\cdot323&=17\tag{1a}\\ 19\cdot391-23\cdot323&=0\tag{1b} \end{align} Applying the Extended Euclidean Algorithm to $$437$$ and $$391$$ $$\begin{array}{r} &&1&8&2\\\hline 1&0&1&-8&17\\ 0&1&-1&9&-19\\ 437&391&46&23&0\\ \end{array}$$ we get $$\gcd(437,391)=23$$ and \begin{align} 9\cdot391-8\cdot437&=23\tag{2a}\\ 19\cdot391-17\cdot437&=0\tag{2b} \end{align} Applying the Extended Euclidean Algorithm to $$437$$ and $$323$$ $$\begin{array}{r} &&1&2&1&5\\\hline 1&0&1&-2&3&-17\\ 0&1&-1&3&-4&23\\ 437&323&114&95&19&0\\ \end{array}$$ we get $$\gcd(437,323)=19$$ and \begin{align} 3\cdot437-4\cdot323&=19\tag{3a}\\ 17\cdot437-23\cdot323&=0\tag{3b} \end{align}

Writing $$\bf{1}$$ as a Linear Combination of $$\bf{323}$$, $$\bf{391}$$, and $$\bf{437}$$

Since $$17$$, $$19$$, and $$23$$ share no common factors, we can write $$1$$ as a linear combination of $$323$$, $$391$$, and $$437$$.

We start by applying the Extended Euclidean Algorithm to $$23$$ and $$17$$, the gcds in $$\text{(2a)}$$ and $$\text{(1a)}$$: $$\begin{array}{r} &&1&2&1&5\\\hline 1&0&1&-2&3&-17\\ 0&1&-1&3&-4&23\\ 23&17&6&5&1&0\\ \end{array}$$ We get that $$\gcd(23,17)=1$$ and $$3\cdot23-4\cdot17=1\tag4$$ Applying $$\text{(1a)}$$ and $$\text{(2a)}$$ to $$(4)$$ yields \begin{align} 1 &=3\cdot\overbrace{23}^\text{(2a)}-4\cdot\overbrace{17}^\text{(1a)}\\ &=3(9\cdot391-8\cdot437)-4(5\cdot391-6\cdot323)\\ &=24\cdot323+7\cdot391-24\cdot437\tag5 \end{align} Equation $$(5)$$ shows how to write $$1$$ as a linear combination of $$323$$, $$391$$, and $$437$$. Using $$\text{(3b)}$$, $$(5)$$ can be reduced to $$1=1\cdot323+7\cdot391-7\cdot437\tag6$$

Writing $$\bf{10473}$$ as a Linear Combination of $$\bf{323}$$, $$\bf{391}$$, and $$\bf{437}$$

We can simply multiply $$(6)$$ by $$10473$$ and reduce using $$\text{(1b)}$$ and $$\text{(2b)}$$: \begin{align} 10473 &=10473\cdot323+73311\cdot391-73311\cdot437\\ &+455\,(19\cdot391-23\cdot323)\tag{7a}\\ &=8\cdot323+81956\cdot391-73311\cdot437\\ &-4313\,(19\cdot391-17\cdot437)\tag{7b}\\ &=8\cdot323+9\cdot391+10\cdot437\tag{7c} \end{align} Explanation:
$$\text{(7a)}$$: reduce the coefficient of $$323$$ using $$\text{(1b)}$$
$$\text{(7b)}$$: reduce the coefficient of $$391$$ using $$\text{(2b)}$$
$$\text{(7c)}$$: a reduced linear combination

The General Solution

The difference of two solutions to $$323x+391y+437z=10473$$ is a solution to the homogeneous equation $$323x+391y+437z=0\tag8$$ Consequences of $$(8)$$:
Since $$\gcd(323,437)=23$$, we have $$23\mid x$$, so WLOG let $$x=23a$$.
Since $$\gcd(391,437)=19$$, we have $$19\mid y$$, so WLOG let $$y=19b$$.
Since $$\gcd(323,391)=17$$, we have $$17\mid z$$.
Note that $$323(23a)+391(19b)=437(17a+17b)$$, so we need $$z=-17a-17b$$.

Therefore, the general solution to $$(8)$$ is $$323(23a)+391(19b)-437(17a+17b)=0\tag9$$ Thus, combining $$\text{(7c)}$$ and $$(9)$$, the general solution to $$323x+391y+437z=10473$$ is $$\bbox[5px,border:2px solid #C0A000]{10473=(8+23a)\,323+(9+19b)\,391+(10-17a-17b)\,437}\tag{10}$$ Looking at $$(10)$$, it appears that $$\text{(7c)}$$ is the only solution with all positive coefficients.

• It would be helpful to clearly explain why that is the general solution (no one has done this yet, and we may be missing that reasoning on the site). – Bill Dubuque Aug 17 at 1:02
• I dont know why everyone is just doing some random calculation and saying that this is the required answer without even bothering to explain how to solve this problem – Math_Freak Aug 17 at 3:36
• @BillDubuque: in the answer cited above, this is discussed in a couple of places. I will try to add something about it here. – robjohn Aug 17 at 5:02
• @Math_Freak: have you read about the Extended Euclidean Algorithm or the implementation cited above? I am working on more explanation to add here, but the more you read about the Extended Euclidean Algorithm, the more these "random calculations" might make sense. – robjohn Aug 17 at 5:05
• @BillDubuque: I tried to expand this answer to explain the role of the homogeneous solution, but it dragged the answer off point and confused the issue. I will expand another answer whose point is the inner workings of the algorithm and not its use. – robjohn Aug 17 at 12:24

Recall that - by linearity - the general solution of a non-homogeneous linear equation is obtained by $$\color{#0a0}{\text{adding}}$$ any particular solution $$\rm P$$ to the general solution $$\rm H$$ of the associated homogeneous equation. We can use this to reduce the solution of a trivariate linear Diophantine equation to the well-known bivariate case as below. Here I have followed the presentation that is implicit in the (unproved) formula applied in Robert's answer, and also appended a complete proof of that (unproven) formula.

Homogeneous solution: $$\ 323 x + 391 y = - 437 z\$$ is solved as below:

$$\gcd(323,391) = 17\mid 437z\,\Rightarrow\, 17\mid z,\$$ so $$\ z = 17 m\,$$ for $$\,m\in\Bbb Z$$

Cancelling $$\,17\,$$ above yields: $$\ \,19x\, +\, 23 y\, = -437m.\,$$ Recursively solving this bivariate case:

$$\ \ \$$ Particular solution: $$\bmod 19\!:\ 4y\equiv 0\iff y\equiv 0,\$$ so $$\ x = {\large \frac{-437m}{19}} = -23m$$

$$\ \ \$$ Homogeneous solution: $$\ 19x+23y = 0\iff {\large \frac{y}x =\, \frac{\!\!-19}{23}}\!$$ $$\iff$$ $$(x,y) = (23k,-19k)$$

$$\ \ \ \ \color{#0a0}{\text{Adding}}\rm\ P\!+\!H\!:$$ $$\ (x,y,z)\, =\, (23k,\, -19(m\!+\!k),\, 17m) =$$ general homogeneous solution.

Particular solution $$\ (x,y,z) = (8,9,10)\$$ is obtained as follows:

$$10473 = 437z + 17(\color{#c00}{19x\!+\!23y}) =: 437z + 17\,\color{#c00}T$$

$$\!\bmod 17\!:\ z \equiv {\large \frac{10473 }{437}\equiv \frac{1}{12} \equiv \frac{18}2\frac{18}6}\equiv 9\cdot 3\equiv 10\$$ so $$\ \color{#c00}T = {\large \frac{10473-437(10)}{17}} = \color{#c00}{359}$$

$$\color{#c00}{19x\!+\!23y = 359}\$$ \Rightarrow \bmod 19\!:\ \begin{align}4y&\equiv -2\\ 2y&\equiv -1\equiv 18\end{align}\!\!\iff y\equiv 9\ so $$\,x = {\large \frac{359-23(9)}{19}} = 8$$

$$\color{#0a0}{\text{Adding}}\rm\ P\!+\!H\!:$$ $$\,\ \bbox[5px,border:1px solid #c00]{(x,y,z) = (8\!+\!23k,\, 9\!-\!19(m\!+\!k),\, 10\!+\!17m)}\:$$ is a general solution.

Below is a complete proof of the cited formula - proved exactly as above.

Theorem  Let $$\,a,b,c\in\Bbb Z\,$$ with gcd $$\,(a,b,c) = 1,\,$$ let gcd $$\, (a,b) =: g,\,$$ and $$\,a' = a/g,\ b' = b/g.$$

Let $$\ \ z_0,\, t_0\in\Bbb Z\,\$$ be any solution of $$\, \ c\,z\:\! +\ g\,t\, =\, d$$
and $$\ u_0,v_0\in\Bbb Z\$$ be any solution of $$\ \, a'u + b'v\, =\, c$$
and $$\ x_0, y_0\in\Bbb Z\$$ be any solution of $$\ \ a'x + b'y =\:\! t_0$$.

Then $$\,ax + by + cz = d\,$$ has the general solution \,\ \begin{align} x &= x_0 + b'k - u_0 m\\ y &= y_0 - a'k - v_0 m\\ z &= z_0 + gm\end{align}\,\ for any $$\,k,m\in\Bbb Z$$

Proof:  Homogeneous solution: $$\ a x + b y = -c z\$$ is solved as below:

$$(a,b) = g\mid cz\,\Rightarrow\, g\mid z,\$$ so $$\ z = g m\,$$ for $$\,m\in\Bbb Z,\,$$ by $$((a,b),c)\! =\! (a,b,c)\!=\!1\,$$ &  Euclid's Lemma.

Cancelling $$\,g\,$$ above yields: $$\ \,a'x\, +\,b' y\, = -cm.\,$$ Recursively solving this bivariate case:

$$\ \ \$$ Particular solution: $$\ (x,y) = (-u_0m,-v_0m)\$$ by $$\,u_0,v_0\,$$ hypothesis scaled by $$\,-m$$.

$$\ \ \$$ Homogeneous solution: $$\ a'x+b'y = 0\iff {\large \frac{y}x =\, \frac{\!\!-a'}{b'}}\!$$ $$\iff$$ $$(x,y) = (b'k,-a'k)$$

$$\ \ \ \ \color{#0a0}{\text{Adding}}\rm\ P\!+\!H\!:$$ $$\ (x,y,z)\, =\, (b'k\!-\!u_0m,\, -a'k\!-\!v_0m,\, gm) =$$ general homogeneous solution.

Particular solution $$\,\ (x,y,z) = (x_0,y_0,z_0)\$$ is obtained as follows:

$$d = cz + g(\color{#c00}{a'x\!+\!b'y}) =: cz + g\,\color{#c00}t\$$ has solution $$\,(z,\color{#c00}t) = (z_0,\color{#c00}{t_0})\,$$ by hypothesis.

and also: $$\, \ \ \ \color{#c00}{a'x\!+\!b'y = t_0}\,\$$ has  as  a  solution: $$\ \, (x,y) = (x_0,y_0)\,$$ by hypothesis.

Therefore $$\,(x,y,z) = (x_0,y_0,z_0)\,$$ is a particular solution.

$$\color{#0a0}{\text{Adding}}\,$$ the Particular and Homogeneous solutions yields the claimed general solution.

Remark  If $$\, e := (a,b,c) > 1\,$$ then $$\,e\mid d\,$$ so cancelling $$e$$ in the equation reduces to the above case.

• Thank you sir for taking the time to explain – Math_Freak Aug 19 at 3:35

Below we show how it can be solved using more general methods for solving systems of Diophantine equations by reducing them to Hermite / Smith triangular / diagonal and related normal forms. If you search on those keywords you should find expositions on these general methods.

Below is one simple way to do so, via this method, except here we need to keep track of the $$3$$ current rows, which are the current row plus the two notated at row end, e.g. rows $$\color{#c00}{[\![5]\!]}$$ snd $$[\![4,2]\!]$$ below.

$$\ \ \ \ \begin{array}{rrrrrl} [\![1]\!] & 437 & 1 & 0 & 0 \\ [\![2]\!] & 391 & 0 & 1 & 0 \\ [\![3]\!] & 323 & 0 & 0 & 1 \\ [\![1]\!]-1\,[\![2]\!]\, \rightarrow\, [\![4]\!] & 46 & 1 & -1 & 0 &[\![3,2]\!]\\ [\![3]\!]-7\,[\![4]\!]\, \rightarrow\, \color{#c00}{[\![5]\!]} &\color{#c00}1 & \color{#c00}{{-}7} & \color{#c00}7 & \color{#c00}1& [\![4,2]\!]\ \ \ \ \ \ \smash{\overbrace{\color{#c00}1 = \color{#c00}7\cdot 437 \color{#c00}{-7}\cdot 391+\color{#c00}1\cdot 323}^{\large \color{#c00}{\text{Bezout}}\text{ Identity}}}\\ [\![2]\!]-8\,[\![4]\!]\, \rightarrow\, [\![6]\!] & 23 & {-}8 & 9 & 0& [\![5,4]\!]\\ [\![4]\!]-2\,[\![6]\!]\, \rightarrow\, \color{#0a0}{[\![7]\!]} & \color{#0a0}0 & \color{#0a0}{17} & \color{#0a0}{{-}19} & \color{#0a0}0&[\![6,5]\!]\ \ \ \ \ \ \color{#0a0}{\text{Null_{\:\!1}}}\\ [\![6]\!]\!\!-23[\![5]\!]\, \rightarrow\,[\![8]\!] & 0 &\!\! 153 & \!\!{-}152 &\! {-}23&[\![7,5]\!]\\ [\![8]\!]-9\,[\![7]\!]\, \rightarrow\, \color{#90f}{[\![9]\!]} & \color{#90f}0 & \color{#90f}0 & \color{#90f}{19} & \!\color{#90f}{{-}23} &[\![7,5]\!]\ \ \ \ \ \ \color{#90f}{\text{Null_{\:\!2}}}\\ \end{array}$$

$$\begin{array}{r r r r r l} 10473\color{#c00}{[\![5]\!]}\, \rightarrow\, [\![a]\!] & 10473 &\!\!\!-73311 &\!\! 73311 &\!\! 10473&\ \ 10473\times \color{#c00}{\text{Bezout}}\text{ Identity}\\ [\![a]\!]\!-\!4313\color{#0a0}{[\![7]\!]}\, \rightarrow\, [\![b]\!] & 10473 &\!\!\!10 &\!\!\! -8636 &\!\! 10473&\ \ \text{use }\color{#0a0}{{\text {Null}}_{\:\!1}}\text{ to reduce coef of }437\\ [\![b]\!]\:\!+\:\!455\color{#90f}{[\![9]\!]}\, \rightarrow\, [\![c]\!] & 10473 &10 & 9 & 8& \ \ \text{use }\color{#90f}{{\text{Null}}_{\:\!2}}\text{ to reduce coef of }391\end{array}$$

A particular solution is: $$\ 10473 = 10\cdot 437 + 9 \cdot 391 + 8\cdot 323\$$ from the prior row, and

the null space is $$\ (z,y,x) = (\color{#0a0}{17,-19,0})m - (\color{#90f}{0,19,-23})k = (17m,-19(m\!+\!k),23k)$$

Compare robjohn's answer, which is similar, but does not explicitly use Hermite row reduction.

• Thank you but I prefer your second solution given below – Math_Freak Aug 19 at 3:37

Three variables doesn't really make as much of a difference as you'd think.

$$323 =17*19$$ and $$391 = 17*23$$ and $$437 = 19*23$$

Let's suppose that $$(x,y,z)$$ and $$(x+a, y+b, z+c)$$ are two solutions to $$323x + 391y + 437z = 10473$$.

Then $$17*19(a) + 17*23(b) + 19*23(c)= 0$$ and so

$$a\equiv 0 \pmod 23$$, and $$b\equiv 0 \pmod 19$$ and $$c\equiv 0 \pmod 17$$

So suppose $$a= 23j; b=19k; c=17m$$

then we must have $$j+k+m = 0$$ and any such combination is possible.

So if $$(x,y,z)$$ is a solution then $$(x + 23j,y+19k,z-17(j+k))$$ will be a solution and that generates all solutions.

Now by Bezout we can solve $$323A + 391B= 17$$ and $$391C + 437D = 23$$ and $$17M+23N = 10473$$

so $$(323A + 391B)M + (391C+437D)N = 10473$$

and $$323AM + 391(BM+CN) + 437DN = 10473$$ is a solution.

So the solution set is $$\{(AM+23j, BM+CN+19k, DN+17m| j+k + m = 0\}$$.

..... .....

Now was the question supposed to be that $$x,y,z$$ must all be positive?

If so:

$$323A+391B =17$$

$$19A + 23B = 1$$

(Argh, I really hate doing this but...)

$$23 - 19 = 4$$

$$3 = 19-4*4 = 19 - 4(23-19) = 19*5 - 4*23$$

$$1 = 4-3 = (23-19)-(19*5 - 4*23) = 5*23- 6*19$$

So we can let $$A=-6$$ and $$B=5$$.

$$391C + 437D = 23$$

$$17C + 19D = 1$$ so

$$19 - 17 = 2$$

$$1=17 - 8*2 = 17- 8(19-17) = 9*17-8*19$$

So we can let $$C= 9$$ and $$D = -8$$.

And for

$$17M+23N = 10473$$

$$23 -17 = 6$$

$$1=3*6 - 17=3(23-17) - 17=3*23 - 4*17$$

So we can let $$M=-4(10473)$$ and $$N=3(10473)$$.

So the solution set is:

$$\{(AM+23j, BM+CN+19k, DN+17m| j+k + m = 0\}=$$

$$\{(24*10473+23j, 7*10473+19k, -24*10473+17m| j+k + m = 0\}$$

To make these monster managable:

Since $$24*10473, 7*10473, -24*10473$$ is a solution then so is

$$24*10473 - 23*2*10473, 7*10473, -24*10473 + 17*2*10473 = -22*10473,7*10473, 10*10473$$ and so is

$$10473, 7*10473 -19*10473, 10*10473= 10473,-125676, 104730$$ and so is

$$10473, -125676+19*6615, 104730-17*6615=10473,9,-7725$$ and so is

$$10473-455*23,9, -7725+455*17= 8,9,10$$

And ... that's the only positive solution. To have $$j + k +m=0$$ then one of $$j,k,m \le -1$$ and $$8-23,9-19, 10-17$$ are all negative.

• I don't see any clear argument that this method yields all solutions of the original equation. – Bill Dubuque Aug 17 at 2:31
• Doesn't it? That yields all.... hmmm, you're right $17a+ 19a$ and $19a+ 23b$ may yield different bases and more solutions. – fleablood Aug 17 at 3:02

$$323x+391y+437z=10473$$

My version of EEA is as follows.

$$\begin{array}{r|r|rrr|l} & & 437 & 391 & 323 \\ \hline & 437 & 1 & 0 & 0 & 437-1\cdot323 = 114\\ & 391 & 0 & 1 & 0 & 391-1\cdot323 = 68\\ & 323 & 0 & 0 & 1 & \\ \hline & 323 & 0 & 0 & 1 & 323-4\cdot 68 = 51\\ & 114 & 1 & 0 & -1 & 114 - 1\cdot 68 = 46\\ & 68 & 0 & 1 & -1 & \\ \hline & 68 & 0 & 1 & -1 & 68-1\cdot 46 = 22\\ & 51 & 0 & -4 & 5 & 51 - 1 \cdot 46 = 5\\ & 46 & 0 & -1 & 1 & \\ \hline & 46 & 1 & -1 & 0 & 46 - 9\cdot 5 = 1\\ & 22 & -1 & 2 & -1 & 22 - 4\cdot 5 = 2\\ & 5 & -1 & -3 & 5 & \\ \hline & 5 & -1 & -3 & 5 & 5-5\cdot 1 = 0\\ & 2 & 3 & 14 & -21 & 2-2\cdot 1 = 0\\ & 1 & 10 & 26 & -45 & \\ \hline & 1 & 10 & 26 & -45 & \\ & 0 & -51 & -133 & 230 & \text{See comments below.}\\ & 0 & -17 & -38 & 69 & \\ \hline & 1 & 10 & 26 & -45 & \\ & 0 & 17 & -19 & 0 & \text{See comments below.}\\ & 0 & 0 & 19 & -23 \\ \hline \end{array}$$

Comments. The "null space" generated by the algorithm tends to be "ugly". Looking at the basis elements pairwise will give a much prettier null space.

So

$$323(-45) + 391(26) + 437(10) = 1$$

and

$$323(-471285) + 391(272298) + 437(104730) = 10473.$$

Hence

$$(x,y,z) = (-471285-23t, 272298-19s+19t, 104730+17s)$$

• We can also use row operations to simplify the general solution - see the final two rows $\,[\![b]\!]$ and $\,[\![c]\!]$ in the Remark in my answer. – Bill Dubuque Aug 18 at 1:47
• @BillDubuque Yes. I did it this way at work (when I worked) because it was quick and easy to do in MATLAB. – steven gregory Aug 18 at 2:59