“*x* mod* y*” is mathematician-speak for “the remainder you’re left with when you try to divide *x* by *y*” – that is, to work it out you take away as many copies of y from x as you can. Eventually you’ll be left with a number smaller than y, and that’s x mod y.

That’s quite a mouthful, but it’s probably easier to do than to describe. For example, 7 mod 3 is 1, because 7-3 = 4, 4-3 = 1, but if you tried to take away 3 from 1 you’d get a number less than 0, so that’s as far as you can go. 8 mod 2 is 0, because subtracting successive copies of 2 from 8 takes you to 6, 4, 2 and then 0, but you can’t go any further. 6 mod 5 is 1, obviously, but 5 mod 6 is 5 because you can’t take away any copies of 6.

Exercise 1:

Explain why “the number you get when you take away the largest multiple of *y* below* x*“, “the number left when you take away copies of *y* from *x* until you can’t do so without going below 0″ and “the remainder when you try to divide *x* by *y*” are all the same thing.

Exercise 2:

Pick some triples of numbers *x _{1}, x_{2}, y* and compute:

a: (

*x*mod

_{1}*y*) + (

*x*mod

_{2}*y*) mod

*y*

b: (

*x*+

_{1}*x*) mod

_{2}*y*

What do you notice?

Now do the same with

c: (*x _{1}* mod

*y*) × (

*x*mod

_{2}*y*) mod

*y*

d: (

*x*×

_{1}*x*) mod

_{2}*y*

(To check you’re doing it right: if you pick* x _{1}* = 5,

*x*= 10,

_{2}*y*= 3 then for a)

*x*mod

_{1}*y*is 2,

*x*mod

_{2}*y*is 1, and so (

*x*mod

_{1}*y*) + (

*x*mod

_{2}*y*) = 3, and (

*x*mod

_{1}*y*) + (

*x*mod

_{2}*y*) mod

*y*= 0. For b),

*(x*) = 15 and 15 mod 3 is 0. For c) (

_{1}+x_{2}*x*

_{1}*mod*

*y*) × (

*x*mod

_{2}*y*) = 2, and 2 mod 3 is 2; for d)

*x*×

_{1}*x*is 50 and 50 mod 3 is 2 because 48 is a multiple of 3. )

_{2}Exercise 3:

For this exercise, it will be very helpful to know about prime numbers and prime factorisation.

Now, write down some “modular multiplication tables”. You’ve probably done ordinary times tables at school; a modular multiplication table for a number y is the same, except that in runs from 0 to y, and you reduce each entry mod y.

For example, a modular multiplication table for 3 is worked out as

(0×0 mod 3) (0 × 1 mod 3) (0×2 mod 3)

(1×0 mod 3) (1 × 1 mod 3) (1×2 mod 3)

(2×0 mod 3) (2 × 1 mod 3) (2×2 mod 3)

which comes to

0 0 0

0 1 2

0 2 1

while for 4 the modular times table looks like

0 0 0 0

0 1 2 3

0 2 0 2

0 3 2 1

Build these tables for a) some prime numbers, b) some composite numbers whose factorisations you know. What do you notice?

(For example: what can you say about how many distinct numbers will turn up in a given row or column, and how many times each number will recur?)