modulo astro

stars tell you

An Introduction to Modulo

When we divide two integers we will have an equation that looks like the following:

A / B = Q with remainder R

A is the dividend
B is the divisor
Q is the quotient
R is the remainder

Sometimes, we are only interested in what the remainder will be when we divide A by B.
For these cases there is an operator called the modulo operator (abbreviated as mod).

Using the same A,B,Q,and R as above, we would have: A mod B = R

We would say this as "A modulo B is congruent to R". Where B is referred to as the modulus.

For example we know: 13/5 = 2 remainder 3
or
13 mod 5 = 3

Visualize modulus with clocks

Observe what happens when we increment numbers by one and then divide them by 3.

0/3=0 remainder 0
1/3=0 remainder 1
2/3=0 remainder 2
3/3=1 remainder 0
4/3=1 remainder 1
5/3=1 remainder 2
6/3=2 remainder 0
...

The remainders start at 0 and increases by 1 each time, until the number reaches one less than the number we are dividing by.
After that, the sequence repeats.

By noticing this, we can visualize the modulo operator by using circles.

We write 0 at the top of a circle and continuing clockwise writing integers 1,2 ... up to to one less than the modulus.

For example, a clock with the 12 replaced by a 0 would be the circle for a modulus of 12.

To find the result of A mod B = ? we can follow these steps:
1. Construct this clock for size B
2. Start at 0 and move around the clock A steps
3. Wherever we land is our solution.
(if the number is positive we step clockwise, if it's negative we step counter-clockwise)

Examples

8 mod 4 = ?

With a modulus of 4 we make a clock with numbers 0,1,2,3
We start at 0 and go through 8 numbers in a clockwise sequence 1,2,3,0,1,2,3,0

We ended up at 0
so:
8 mod 4 = 0

7 mod 2 = ?

With a modulus of 2 we make a clock with numbers 0,1
We start at 0 and go through 7 numbers in a clockwise sequence 1,0,1,0,1,0,1

We ended up at 1
so:
7 mod 2 = 1

-5 mod 3 = ?

With a modulus of 3 we we make a clock with numbers 0,1,2
We start at 0 and go through 5 numbers in counter-clockwise sequence (5 is negative) 2,1,0,2,1

We ended up at 1
so:
-5 mod 3 = 1

Conclusion

If we have A mod B and we increase A by a multiple of B, we will end up in the same spot
i.e.
A mod B = (A + K * B) mod B for any integer K.

For example:
3 mod 10 = 3
13 mod 10 = 3
23 mod 10 = 3
33 mod 10 = 3

Notes to the Reader

mod in programming languages and calculators

Many programming languages, and calculators, have a mod operator, typically represented with the % symbol.
If you calculate the result of a negative number, some languages will give you a negative result.
e.g. -5 % 3 = -2.

In a future article we will explain, why this happens, and what it means.

Congruence Modulo

You may see an expression like:

A ≡ B (mod C)

This says that A is congruent to B modulo C. It is similar to the expressions we used here, but not quite the same.

In the next article we will explain, what it means, and how it is related to the expressions above.

The best way to introduce modular arithmetic is to think of the face of a clock.

The numbers go from 1 to 12, but when you get to "13 o'clock", it actually becomes 1 o'clock again (think of how the 24 hour clock numbering works). So 13 becomes 1, 14 becomes 2, and so on.

This can keep going, so when you get to "25 o'clock'', you are actually back round to where 1 o'clock is on the clock face (and also where 13 o'clock was too).

So in this clock world, you only care where you are in relation to the numbers 1 to 12. In this world, 1,13,25,37,… are all thought of as the same thing, as are 2,14,26,38,… and so on.

What we are saying is "13=1+ some multiple of 12", and "38=2+ some multiple of 12", or, alternatively, "the remainder when you divide 13 by 12 is 1" and "the remainder when you divide 38 by 12 is 2''. The way we write this mathematically is 13≡1 mod 12, 38≡2 mod 12, and so on. This is read as "13 is congruent to 1 mod (or modulo) 12" and "38 is congruent to 2 mod 12".

But you don't have to work only in mod 12 (that's the technical term for it). For example, you could work mod 7, or mod 46 instead if you wanted to (just think of clocks numbered from 1 to 7 and 1 to 46 respectively; every time you get past the biggest number, you reset to 1 again).

Let's go back to the normal clock face with the numbers 1 to 12 on it for a moment. Mathematicians usually prefer to put a 0 where the 12 would normally be, so that you would usually write (for example) 24≡0 mod 12 rather than 24≡12 mod 12, although both of these are correct. That is, we think of a normal clock face as being numbered from 0 to 11 instead. This makes sense: we'd normally say that 24 leaves a remainder of 0 when we divide by 12, rather than saying it leaves a remainder of 12 when we divide by 12!

Let's be a bit more formal. In general, if you are working in mod n (where n is any whole number), we write a≡b mod n if a and b leave the same remainder when you divide them by n. This is the same as saying that we write a≡b mod n if n divides a�'b. (Look at what we did earlier to see that this definition fits with our examples above.)

So far, we've only talked about notation. Now let's do some maths, and see how congruences (what we've described above) can make things a bit clearer.

Here are some useful properties. We can add congruences. That is, if a≡b mod n and c≡d mod n, then a+c≡(b+d) mod n. Why is this? Well, a≡b mod n means that a=b+kn, where k is an integer. Similarly, c≡d mod n means that c=d+ln, where l is an integer. So a+c=(b+kn)+(d+ln)=(b+d)+(k+l)n, so a+c≡(b+d) mod n. For example, 17≡4 mod 13, and 42≡3 mod 13, so 17+42≡4+3≡7 mod 13. Note that both of the congruences that we're adding are mod n, and so is the answer - we don't add the moduli.

Now you prove that if a≡b mod n and c≡d mod n then a�'c≡(b�'d) mod n. Also, prove that we can do something similar for multiplication: if a≡b mod n and c≡d mod n, then ac≡bd mod n. You can prove this in the same way that we used above for addition. Again, both of the congruences that we're multiplying are mod n, and so is the answer - we don't multiply the moduli. Can you come up with an example to disprove the claim that a≡b mod n and c≡d mod m means that ac≡bd mod mn?

Division is a bit more tricky: you have to be really careful. Here's an example of why. 10≡2 mod 8. But if we "divide both sides by 2", we'd have 5≡1 mod 8, which is clearly nonsense! To get a true congruence, we'd have to divide the 8 by 2 as well: 5≡1 mod 4 is fine. Why? Well, a≡b mod n means that a=b+kn for some integer n. But now this is a normal equation, and if we're going to divide a by something, then we have to divide all of the right-hand side by 2 as well, including kn. In general, it's best not to divide congruences; instead, think about what they really mean (rather than using the shorthand) and work from there.

Things are quite special if we work mod p, where p is prime, because then each number that isn't 0 mod p has what we call an inverse (or a multiplicative inverse , if we're being fancy). What that means is that for each a≢0 mod p, there is a b such that ab≡1 mod p.

Let's think about an example. We'll work mod 7. Then really the only non-zero things are 1,2,3,4,5 and 6 (because every other whole number is equivalent to one of them or 0). So let's find inverses for them. Well, 1 is pretty easy: 1�-1≡1 mod 7. What about 2? 2�-4≡1 mod 7. So 4 is the inverse of 2. In fact, we can also see from this that 2 is the inverse of 4 - so that's saved us some work! 3�-5≡1 mod 7, so 3 and 5 are inverses. And finally, 6�-6≡1 mod 7, so 6 is the inverse of itself. So yes, each of the non-zero elements mod 7 has an inverse. Try some primes out yourself: 11 and 13 are fairly small! If you're feeling confident, see whether you can discover which numbers have inverses mod 4, or mod 6, or mod 8. What about mod 15? Do you notice any patterns?

To prove this, things are going to get a tiny bit more tricky, so I'm going to save the proof for the end and first give an example of using congruences to do useful mathematics.

Suppose we're given the number 11111111 and someone asks us whether it's divisible by 3. We could try to actually divide it. But you probably know a much easier method: we add up the digits and see whether that's divisible by 3. There's a whole article about this sort of divisibility test .