Skip over navigation
Cambridge University Faculty of Mathematics NRich logo
menu search
  • Teachers expand_more
    • Early years
    • Primary
    • Secondary
    • Post-16
    • Events
    • Professional development
  • Students expand_more
    • Primary
    • Secondary
    • Post-16
  • Parents expand_more
    • Early Years
    • Primary
    • Secondary
    • Post-16
  • Problem-Solving Schools
  • About NRICH expand_more
    • About us
    • Impact stories
    • Support us
    • Our funders
    • Contact us
  • search

Or search by topic

Number and algebra

  • The Number System and Place Value
  • Calculations and Numerical Methods
  • Fractions, Decimals, Percentages, Ratio and Proportion
  • Properties of Numbers
  • Patterns, Sequences and Structure
  • Algebraic expressions, equations and formulae
  • Coordinates, Functions and Graphs

Geometry and measure

  • Angles, Polygons, and Geometrical Proof
  • 3D Geometry, Shape and Space
  • Measuring and calculating with units
  • Transformations and constructions
  • Pythagoras and Trigonometry
  • Vectors and Matrices

Probability and statistics

  • Handling, Processing and Representing Data
  • Probability

Working mathematically

  • Thinking mathematically
  • Developing positive attitudes
  • Cross-curricular contexts

Advanced mathematics

  • Decision Mathematics and Combinatorics
  • Advanced Probability and Statistics
  • Mechanics
  • Calculus

For younger learners

  • Early Years Foundation Stage

Data Chunks

Age 14 to 16
Challenge Level Yellow starYellow starYellow star
  • Problem
  • Getting Started
  • Student Solutions
  • Teachers' Resources

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?

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?

  • Tech help
  • Accessibility Statement
  • Sign up to our newsletter
  • Twitter X logo

The NRICH Project aims to enrich the mathematical experiences of all learners. To support this aim, members of the NRICH team work in a wide range of capacities, including providing professional development for teachers wishing to embed rich mathematical tasks into everyday classroom practice.

NRICH is part of the family of activities in the Millennium Mathematics Project.

University of Cambridge logo NRICH logo