Linear Diophantine Equation/Examples/17x + 15y = 143

From ProofWiki
Jump to navigation Jump to search

Example of Linear Diophantine Equation

The linear diophantine equation:

$17 x + 15 y = 143$

has the general solution in positive integers:

$\tuple {x, y} = \tuple {4, 5}$


Proof

Using the Euclidean Algorithm:

\((1):\quad\) \(\displaystyle 17\) \(=\) \(\displaystyle 1 \times 15 + 2\)
\((2):\quad\) \(\displaystyle 15\) \(=\) \(\displaystyle 7 \times 2 + 1\)

Thus we have that:

$\gcd \set {17, 15} = 1$

which is (trivially) a divisor of $143$.

So, from Solution of Linear Diophantine Equation, a solution exists.


Next we find a single solution to $17 x + 15 y = 143$.

Again with the Euclidean Algorithm:

\(\displaystyle 1\) \(=\) \(\displaystyle 15 - 7 \times 2\) from $(2)$
\(\displaystyle \) \(=\) \(\displaystyle 15 - 7 \times \paren {17 - 1 \times 15}\) from $(1)$
\(\displaystyle \) \(=\) \(\displaystyle 8 \times 15 - 7 \times 17\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle 143\) \(=\) \(\displaystyle 143 \times \paren {8 \times 15 - 7 \times 17}\)
\(\displaystyle \) \(=\) \(\displaystyle 1144 \times 15 - 1001 \times 17\)


and so:

\(\displaystyle x_0\) \(=\) \(\displaystyle 1001\)
\(\displaystyle y_0\) \(=\) \(\displaystyle 1144\)

is a solution.


From Solution of Linear Diophantine Equation, the general solution is:

$\forall t \in \Z: x = x_0 + \dfrac b d t, y = y_0 - \dfrac a d t$

where $d = \gcd \set {a, b}$.

In this case:

\(\displaystyle x_0\) \(=\) \(\displaystyle 1001\)
\(\displaystyle y_0\) \(=\) \(\displaystyle 1144\)
\(\displaystyle a\) \(=\) \(\displaystyle 17\)
\(\displaystyle b\) \(=\) \(\displaystyle 15\)
\(\displaystyle d\) \(=\) \(\displaystyle 1\)


giving:

\(\displaystyle x\) \(=\) \(\displaystyle -1001 + 15 t\)
\(\displaystyle y\) \(=\) \(\displaystyle 1144 - 17 t\)


Both $x$ and $y$ must be non-negative integers.

Hence:

\(\displaystyle 1144 - 17 t\) \(\ge\) \(\displaystyle 0\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle 17 t\) \(\le\) \(\displaystyle 1144\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle t\) \(\le\) \(\displaystyle \dfrac {1144} {17} = 67 + \dfrac 5 {17}\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle t\) \(\le\) \(\displaystyle 67\)

and:

\(\displaystyle -1001 + 15 t\) \(\ge\) \(\displaystyle 0\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle 15 t\) \(\ge\) \(\displaystyle 1001\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle t\) \(\ge\) \(\displaystyle \dfrac {1001} {15} = 66 + \dfrac {11} {15}\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle t\) \(>\) \(\displaystyle 66\)


Hence $t = 67$ and so:

\(\displaystyle x\) \(=\) \(\displaystyle -1001 + 15 \times 67\)
\(\displaystyle \) \(=\) \(\displaystyle 4\)
\(\displaystyle y\) \(=\) \(\displaystyle 1144 - 17 \times 67\)
\(\displaystyle \) \(=\) \(\displaystyle 5\)


The required solution is therefore:

$x = 4, y = 5$

$\blacksquare$


Historical Note

This exercise was originally couched in the language of a person making a purchase of:

$x$ items of commodity $A$, costing $17$ monetary units each

and:

$y$ items of commodity $B$, costing $15$ monetary units each

for a total outlay of $143$ monetary units.


It is apparent in this context that both $x$ and $y$ must be non-negative, and (in the specific wording of the question) can be interpreted as actually strictly positive.

Such exercises are usually (as this one is) specifically crafted so as to allow for only one solution.


Sources