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.