Just looking at algebra, a Diophantine equation is one like \[4x+7y = 19 \tag{EQ 1}\] and the values for \(x\) and \(y\) must be integers.
While these don't seem impossible to solve, it does appear that a lot of guessing might be involved. Additionally, the problem might specify that the answer should be positive numbers. No guarantee of a solution is provided.
So how might one of these equations arise in context?
Suppose that chocolate bunnies are sold in two package sizes. One size contains 4 bunnies and the other size contains 7 bunnies.
We want to buy some for a kid party where we will have 19 children and we want each child to get a bunny. Can we buy exactly 19 bunnies,
and if so, how many packages of each should we purchase. This is exactly EQ 1.
Yet another example, nearly the same but worded to be as confusing as possible.
A brand of cereal in small boxes is sold in packages of either 7 or 11. What is the largest integer
\( n\) such that there is no way to buy exactly \( n\) small boxes of cereal?
Now we have the equation $$7x+11y=n \tag{EQ 2}$$ and we want \(n\) such that the equation is unsolvable with integer values but \(n+1\) and every
integer thereafter has a solution. It's hard to believe that these are nearly the same problem.
The simple answer to the second problem is "The largest nonrepresentable integer is \(ab-a-b.\)" In this instance, \(a=7; b=11\). The crazy part is that for every larger integer, you can buy exactly a correct number of packages to get the number of cereal boxes desired.
$$ax+bx=c \tag{EQ 3}$$ If the greatest common divisor, gcd, of values a and b will divide c, then a solution exists. It may well be composed of one negative and one positive value, but it exists nonetheless. An algorithm for the gcd(a,b) is given here in javascript and python.
//javascript
const gcd = (a,b) => {
if(a==0){return b;}
return gcd(b%a,a);
}
#python
def gcd(a,b):
if(a==0):return b
return gcd(b%a,a)
There is one other algorithm that is needed and it is the Extended Euclidian. In this code, returned values \(x\) and \(y\) are integer solutions to gcd(a,b)=x*a+y*b.
//javascript
function xgcd(a, b) {
if (b === 0) return [a, 1, 0];
let [g, x1, y1] = xgcd(b, a % b);
return [g, y1, x1 - Math.floor(a / b) * y1];
}
//js usage:
a=7; b=11; c=60;
[n,x,y]=xgcd(7,11);
console.log(`gcd(a,b)=${n}, x=${x}, y=${y}`)
----------------
#python
def xgcd(a, b):
'''extended Euclidean for python3. Returns gcd(a,b),x,y
gcd(a,b) = x*a + b*y'''
if b == 0:
return a ,1, 0
else :
q, r = divmod (a, b)
g,x, y = xgcd(b, r)
return g,y, x - q * y
#python usage:
[n,x,y]=xgcd(a,b)
print(f"xgcd = {n,x,y}")
Obviously if the gcd(a,b) did not divide c, we can stop - there is no solution. But assuming that a solution exists, we might as well use the xgcd(a,b) algorithm and get the gcd(a,b) and \(x\) and \(y\). The xgcd(a,b) returns \((x\),\(y)\) for this equation: $$gcd(a,b) = ax_0+by_0 \tag{EQ 4}$$ which allows us to write a particular solution and identify variables \( x_p,y_p \). $$a\left(x_0\cdot \frac{c}{gcd(a,b)}\right) + b\left(y_0\cdot\frac{c}{gcd(a,b)}\right)=c$$ $$x_p = \left(x_0\cdot \frac{c}{gcd(a,b)}\right)$$ $$y_p = \left(y_0\cdot\frac{c}{gcd(a,b)}\right)$$
There are many solutions! \( -\infty < t < +\infty \)
Note carefully the negative sign in the expression for \(y \). $$x = x_p + \frac{b}{gcd(a,b)}\cdot t$$ $$y = y_p - \frac{a}{gcd(a,b)}\cdot t$$
Assume \( n>ab-a-b.\) Then \(n+a>ab-b=b(a-1). \)
So \( n+a \) is strictly larger than the largest multiple of \(b\) less than \(ab\). Let \(y\) be the integer \( 0\le y \le a-1 \) such that $$ yb\equiv n\pmod a $$
Then \( a | (n-yb) \) and is non-negative.
(Why it is non-negative.)
Since \( yb \le (a-1)b \) and \( n>ab-a-b, \) we have
$$
n-yb > ab-a-b-(a-1)b = ab-a-b-ab+b=-a
$$
$$
\therefore n-yb>-a
$$
\( n-yb \) is a multiple of \(a\) and thus must be \( \ge 0 \). So \(\frac{n-yb}{a} \) is a non-negative integer,
hence representable. \( \square \)