Stage: 4 Challenge Level:
Tom from Bristol Grammar School sent us his
work on this problem.
We have an equation of the form $ax+by=c$ where all of the unknowns
are integers, and we know $a$ and $b$ (the lengths of our coloured
rods) and $c$ (the length of our white rod) and want to find $x$
and $y$. In this problem we are interested in the existence of $x$
and $y$ (do there exist integers that solve the problem?).
In our initial case we have $5x+3y=1$ (or $-1$, we can reverse the
signs of $x$ and $y$ to negate the equation, so this does not
matter). Clearly this equation has solutions, one of which is
Now, in our equation $ax+by=1$ let the highest common factor of $a$
and $b$ be $d$ with $a=da^\prime$ and $b=db^\prime$ ($a^\prime$ and
$b^\prime$ both integers also). Our equation becomes $d(a^\prime
x+b^\prime y)=1$. However, the only factors of 1 are $\pm 1$, so
$d=1$. Therefore, for our equation to have any solutions, $a$ and
$b$ cannot have any common factors (are coprime), so, for example,
$a=3$, $b=6$ will not work because they both share factor $3$.
Interestingly, this means we can make $(a^\prime x+b^\prime y)$
whatever value we choose, because $a^\prime$ and $b^\prime$ must be
coprime (with their common factors extracted out as $d$), and we
can choose $x$ and $y$ to make $a^\prime x+b^\prime y=1$ and then
multiply them by anything to get any other integer.
We can extend this logic to the general form $ax+by=c$, so
$d(a^\prime x+b^\prime y)=c$. Therefore, we will have solutions if
and only if $d$ is a factor of $c$ (since $a^\prime x+b^\prime y$
can be anything). I'll complete my solution with a few examples.
$54x+36y=47$ has no solutions, because $18$ (the highest common
factor of $36$ and $54$) does not divide $47$. $30x+25y=10$ has
solutions because $5$ does divide $10$ (for example, $x=2$,
$y=-2$). With actual numbers in $a$, $b$, $c$, the fact we
established above becomes fairly obvious, because we can divide
through by the highest common factor to get $a^\prime$ and
$b^\prime$ (here $6$ and $5$), and because they are coprime, we can
find $x$, $y$ with $6x+5y=1$ so multiplying $x$ and $y$ by $(c/d)$
gives our solution.
This is an example of a "linear Diophantine equation", a concept in
Tom noticed that if $a^\prime$and
$b^\prime$ are coprime then we can find integers $x$ and $y$ such
that $a^\prime x+b^\prime y=1$. This result is sometimes known as
Bezout's Theorem; can you find a proof?