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

Solution 1:

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 $\ \color{#90f}{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\overset{(g,\,c)=1}\Rightarrow\! g\mid z,\ $ so $\ z = g m,\,m\in\Bbb Z,\,$ by $(g,c)\! =\! (a,b,c)\!=\!1\,$ & $ $ Euclid's Lemma.

Cancel $\,g\,$ in $\,ax+by = -cz\,$ $\Rightarrow \,a'x\, +\,b' y\, = -cm.\, $ Recursively solving this bivariate case:

$\ \ \ $ Particular solution: $\ (x,y) = (-u_0m,-v_0m)\ $ by $\,\color{#90f}{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.

Solution 2:

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

Solution 3:

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.

Solution 4:

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.

Solution 5:

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.