Copyright © University of Cambridge. All rights reserved.
'Data Chunks' printed from https://nrich.maths.org/
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?