Copyright © University of Cambridge. All rights reserved.

'Data Chunks' printed from https://nrich.maths.org/

Show menu


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?