5
$\begingroup$

Are there any real life applications of linear Diophantine equations? I am looking for examples which will motivate students.

$\endgroup$
3
  • $\begingroup$ What does [elementary-set-theory] have to do with this? $\endgroup$
    – Asaf Karagila
    Aug 15, 2013 at 16:17
  • 1
    $\begingroup$ I believe I heard of a student going on to work for an airline and doing efficiency work for them. Basically airlines need to know how to shuffle their pilots and stewards/stewardesses around so that they aren't short handed and so that they don't have a bunch sitting on the ground. So, they had a team of mathematicians figure out all the logistics using Diophantine equations (and working in integers since you can't have half a pilot). $\endgroup$
    – Brent J
    Aug 15, 2013 at 16:30
  • $\begingroup$ @Brent it sounds like more of an optimization problem, I wonder if there is any real-life example of a diophantine equality as opposed to an inequality? I'm trying to think of some physical example where the units are quantized. The kinetic energy of a stone dropped from some floor of a building? ... in a vacuum? $\endgroup$ Aug 16, 2013 at 0:17

1 Answer 1

4
$\begingroup$

Real life applications of Diophantine equations can occur very generally when we want to understand a system, whose state can be expressed in terms of a polynomial and depends only on discrete, integer values.

General examples

We might know that Alice and Bob respectively produce exactly $5$ and $3$ identical widgets per day, and that together, they had made $45$ widgets. Thus, the $2$-degree linear Diophantine equation, $5a+3b=45$, expresses $a,b$, which are respectively the number of days that Alice and Bob had worked. Solving this equation shows us that Alice and Bob had respectively worked $3$ and $10$ days, or $6$ and $5$ days, or that one of them had not worked at all. However, this logic would falter if the variables were not constrained to be integers.

Another example comes from a possibly apocryphal story of Chinese generals counting their troops. Instead of soldiers being counted directly, they would be told to stand in an array with $3$ to a row, then repositioned into rows of $5$ and again with rows of $7$. The remaining soldiers from each array, who did not make up a whole row were counted, which would determine the total number, modulo some number. The method may have been intended for efficiency or so that the true number remained hidden from unintended, but mathematically uneducated, audiences. For example, if we knew that the $3$, $5$ and $7$-to-a-row arrays respectively had $2$, $4$ and $6$ excess soldiers, would it be sensible to attack this unit with a force of $103$ equally matched soldiers?

No, it would not, since we can deduce that the total number is at least $n=104$. This problem can be framed as a system of congruences or, equivalently, with simultaneous linear Diophantine equations.

$$\begin{align}n&=3a+2 \\ n&=5b+4\quad \Rightarrow \quad n=104+105k \\ n&=7c+6 \end{align}$$

It is no coincidence that this method involves the 'Chinese remainder theorem'. The origin of the name is discussed on Stackexchange: History of Science and Math.

Field-specific examples

  • Chemistry. Balancing chemical equations is very similar to the earlier example with Alice and Bob's widgets. An example that I have encountered in real life was that a chemical was known to have a mass of $158$ atomic units. If it is solely composed of carbon, hydrogen and oxygen, whose masses are respectively $12$, $1$ and $16$ units, what possible chemical formulas could the chemical have? This is equivalent to the linear Diophantine equation, $12c+1h+16o=158$, which has solutions including $(10,22,1)$, e.g., decanol and $(9,18,2)$, e.g., nonanoic acid. Chemical applications of Diophantine equations are discussed here.

  • Physics. Real life geometric problems can involve Diophantine equations. For example, a gate is built upright, next to a cattle-grid, such that the gate's and cattle-grid's negligibly thin poles are all parallel and spaced by $10\,\mathrm{cm}$ from their nearest neighbour, and there is a pole where the gate and cattle-grid meet. This is similar to the image below, credit to https://www.solargatesystems.co.uk/. Can a $1.3\,\mathrm{m}$ rod be attached with its end points on the gate and cattle-grid, such that it is perpendicular to the existing poles? Yes, since $x^2+y^2=13$ has a solution in integers. However, a $1.4\,\mathrm{m}$ rod cannot.

                                
  • Cryptography. The field of elliptic curve cryptography, ECC, is concerned with calculations in finite fields and $3$rd degree, $2$-variable Diophantine equations.

  • Computational complexity theory. Matiyasevich's theorem states that a set is recursively enumerable if and only if it is also Diophantine. So then, the complexity class, RE, of recursively enumerable problems also correspond with Diophantine equations. These include the Halting problem. Generally, many problems from other branches of math can reframed in terms of Diophantine equations, including dynamical systems, number theory, modular arithmetic etc.

Further reading

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.