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 $5 x + 3 y = 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 $(x, y) = (2, - 3)$ .

Now, in our equation $ax + by = 1$ let the highest common factor of $a$ and $b$ be $d$ with $a = da'$ and $b = db'$ ( $a'$ and $b'$ both integers also). Our equation becomes $d (a' x + b' 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' x + b' y)$ whatever value we choose, because $a'$ and $b'$ must be coprime (with their common factors extracted out as $d$ ), and we can choose $x$ and $y$ to make $a' x + b' 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' x + b' y) = c$ . Therefore, we will have solutions if and only if $d$ is a factor of $c$ (since $a' x + b' y$ can be anything). I'll complete my solution with a few examples. $54 x + 36 y = 47$ has no solutions, because 18 (the highest common factor of 36 and 54) does not divide 47. $30 x + 25 y = 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'$ and $b'$ (here 6 and 5), and because they are coprime, we can find $x$ , $y$ with $6 x + 5 y = 1$ so multiplying $x$ and $y$ by $(c / d)$ gives our solution.

This is an example of a "linear Diophantine equation", a concept in number theory.

Tom noticed that if a' and b' are coprime then we can find integers x and y such that a'x+b'y=1. This result is sometimes known as Bezout's Theorem; can you find a proof?