You may also like

Euler's Squares

Euler found four whole numbers such that the sum of any two of the numbers is a perfect square...

Diophantine N-tuples

Can you explain why a sequence of operations always gives you perfect squares?

There's a Limit

Explore the continued fraction: 2+3/(2+3/(2+3/2+...)) What do you notice when successive terms are taken? What happens to the terms if the fraction goes on indefinitely?

Data Chunks

Age 14 to 16
Challenge Level

Tom firstly showed that we can't solve it for anything other than multiples of the highest common factor of the length:

Suppose we can send data chunks of length $a$ or $b$, and $c$ is our slot size. We can write an equation $ax+by=c$ where $x$ and $y$ are positive integers. If this equation has solutions for $x$ and $y$, we can fill a slot size of $c$ exactly. However because $x$ and $y$ must be positive, we have to be careful. Let $\text{HCF}(a,b)=d$. First, consider an ordinary (with negative solutions) linear diophantine equation (as in the solution to this question ). So we know this cannot have solutions unless $d$ divides $c$.

Tim called $a$ and $b$, $p$ and $q$ and completed the problem for us, finding that we cannot make $pq-p-q$, but we can make all the numbers after it, as shown below:

Write: $$pq-p-q=xp+yq$$
So: $$0=q(1+y) (\text{mod } p)$$
Since $q$ is non-zero,$$ y=-1 (\text{mod } p)$$
If we try $y=p-1$, then $$pq-p-q=xp+pq-q$$
$$0=p(x+1)$$
But this makes $x$ negative, which is impossible. If we try to make $y$ larger, then $x$ has to be smaller, and so there is no solution.

To make all the numbers bigger than this, firstly we notice that we can multiply through by a constant, and so find x and y such that:
$$px+qy=c$$ for all $c$.

Precisely one of $x$ and $y$ must be positive, so if we add $pq$, then for any $c$ we will have:
$$px'+qy'=c+pq$$
With $x'$ and $y'$ at least $0$. In fact, we can find them so they have to be at least $1$, since if one of them was $0$ (for example, $y'$) then: $$px'=c+pq$$ But $c$ would have to be a multiple of $p$ also ($c=bp$) so we could write: $$c+pq=bp+pq$$ So we can choose $x'=b$ and $y'=q$.

But we only need $x'$ and $y'$ to be at least $0$, so we can subtract $(p+q)$ from each side to get (for any $c$ that is at least $1$):
$$c+pq-p-q=px'+qy'$$
With $x'$ and $y'$ both at least $0$.

To learn more about modular arthmetic, why not read the articles linked to in the question?