#### You may also like ### DOTS Division

Take any pair of two digit numbers x=ab and y=cd where, without loss of generality, ab > cd . Form two 4 digit numbers r=abcd and s=cdab and calculate: {r^2 - s^2} /{x^2 - y^2}. ### Common Divisor

Find the largest integer which divides every member of the following sequence: 1^5-1, 2^5-2, 3^5-3, ... n^5-n. ### Hypotenuse Lattice Points

The triangle OMN has vertices on the axes with whole number co-ordinates. How many points with whole number coordinates are there on the hypotenuse MN?

# Different by One

##### Age 14 to 16 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 $(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^\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 number theory.

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?