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
Age 16 to 18
Article by Peter Zimmerman

Published 1998 Revised 2008

Modulus Arithmetic and a Solution to Differences


This short article gives an account of modulus arithmetic which often provides a good method for solving problems. The method is applied here to the following problem, called "Differences ", which appeared in October 1998.

If a, b, c and d are integers, show that the product
(a -b)(b -c)(c - a) is divisible by 2 and that the product
(a -b)(a - c)(a - d)(b -c)(b - d)(c - d)is divisible by 3 and not by 5.

How many integers do you need to ensure that the product of all the differences is divisible by 5?

Consider the integers a, b and c. Each is either odd or even. We can state the following rules about subtraction with odd and even numbers:

Odd - Odd = Even
Odd - Even = Odd
Even - Odd = Odd
Even - Even = Even

Also, any number with an even number as a factor must itself be even (as 2 must be a factor).

Now consider the possibilities for a, b and c. Let x = (a-b)(b-c)(c-a).

1. a odd, b odd, c odd
x = (odd-odd)(odd-odd)(odd-odd)
x = even * even * even
Therefore x must be even (in fact divisible by 8).

2. a odd, b odd, c even
x = (odd-odd)(odd-even)(even-odd)
x = even * odd * odd
Therefore x is even.

3. a odd, b even, c even
x = (odd-even)(even-even)(even-odd)
x = odd * even * odd
Therefore x is even.

4. a even, b even, c even
x = (even-even)(even-even)(even-even)
x = even * even * even
Therefore x is even (divisible by 8 again).

These are the only four distinct possibilities, as a, b and c are effectively interchangeable. For example, having [a even, b even, c odd] is equivalent to situation 3 and will yield the same result.

This result can be generalised to test for divisibility by numbers other than 2. Notice that in order for (a-b)(b-c)(c-a) to be even, the difference inside one of the pairs of brackets must be even. This will occur if either both numbers are odd, or both are even. For example, (a-b) is even if either a and b are both even, or if they are both odd. As there are only two possibilities for each of a, b and c (each can be even or odd), it is inevitable that either at least two are even, or at least two or odd.

If you set a as even and b as odd, then it does not matter what you set for c.

If c is even, (c-a) is even. If c is odd, (b-c) is even. You can see that when you have 3 numbers and only 2 states to put them, at least two of the numbers will be in the same state. To provide a comparison, imagine asking a crowd of people when their birthdays are. As there are 366 possible dates for a birthday (including February 29 as a possibility), you need only ask at most 367 people before you find two people with the same birthday.

This result can be extended to when there are three possible states, as in the next part of the problem. In order to show this effectively, it is best to use modulo 3 arithmetic. The three states, or values, for a, b, c and d are therefore 0, 1 and 2.

Modulo arithmetic is technically an undergraduate subject in mathematics (although I believe some A-level syllabuses still contain it). However, it is a relatively simple subject and can easily be understood by a Key Stage 3 student. In general, modulo n arithmetic involves writing the remainder of the number when it is divided by n, rather than the actual number itself. For example, the number 28 under modulo 3 arithmetic is 1 (because 28 leaves remainder 1 when divided by 3), while the number 33 has value 0. Every number can be written as 0, 1 or 2.

Let y = (a-b)(a-c)(a-d)(b-c)(b-d)(c-d). In order for y to be divisible by 3, one of the differences in the brackets must itself be divisible by 3.

Suppose this bracket is (p-q). Under modulo 3 arithmetic, this means that the difference must have value 0 - in other words, p and q must have the same values (both 0, both 1 or both 2). As there are 4 numbers (a, b, c, d) but only 3 possible states, at least 2 numbers must have the same state. Therefore the difference between these numbers will be 0 (under mod 3) and the corresponding bracket will have value 0, making the number y divisible by 3.

The number y is not necessarily divisible by 5 because under mod 5 arithmetic there are five possible values (0, 1, 2, 3, 4) for the integers a, b, c, d.

Each integer can therefore take a different value, and none of the differences in the brackets need have the value 0. The number y would then not be divisible by 5.

A simple counter-example is to set a=5, b=4, c=3, d=2.
Therefore
(a-b)(a-c)(a-d)(b-c)(b-d)(c-d) = (5-4)(5-3)(5-2)(4-3)(4-2)(3-2) = 1 * 2 * 3 * 1 * 2 * 1 = 12 which is not divisible by 5.

This counter-example alone shows that the product is not necessarily divisible by 5, without the need for a general proof (given above) !

Using the logic discussed above, it can be seen that six integers are required for the product of all the differences to be divisible by 5. Under modulo 5 arithmetic, there are 5 possible values for the integers to take. Therefore, if there are 6 integers, at least two must have the same value. The difference of those two integers will be 0 (under modulo 5 arithmetic) and so the product of the differences will also be 0, meaning that the product is divisible by 5.

In general, to ensure that the product of all the differences of a number of integers is divisible by an integer n, you need (n+1) integers. Under modulo n arithmetic, there are n possible values for the integers to take (0, 1, ... n-2, n-1). Therefore if there are (n+1) integers, at least two must take the same value and so the product of the differences will be 0, meaning it is divisible by n.



You may also like

Purr-fection

What is the smallest perfect square that ends with the four digits 9009?

Old Nuts

In turn 4 people throw away three nuts from a pile and hide a quarter of the remainder finally leaving a multiple of 4 nuts. How many nuts were at the start?

Mod 7

Find the remainder when 3^{2001} is divided by 7.

  • 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