Cookies, clocks and soldiers: modular arithmetic!

Introduction and the 7 dwarfs

It was October when one of my professors entered in the lesson room and said: “Once upon a time, Snow White wished to prepare cookies for the seven dwarfs. Obviously…with some conditions. She wanted to prepare the least number of cookies such that dividing them into 2 dwarfs there would remain only one, dividing them into 3 dwarfs there would remain only one and so on for 4,5 and 6 dwarfs but…dividing them into all the 7 dwarfs, there would not remain any cookie.” This problem generated, of course, hilarity and some puzzled faces appeared in the room because of the nonsense of the story and because of the absurdity of the question. It was one of the first lessons during my first year at University and I honestly remained astonished.

Since for the moment it is not very important, we’re not going to talk of Snow White’s OCD but we will focus on the mathematical side of the story. What the professor wants is the smaller positive integer number (a number of the set 0,1,2,…) such that, if you divide it by 2,3,4,5 and 6, you get 1 as remainder and, if you divide it by 7, the remainder is 0.

It seems to be only an hard calculation and of course it is! But, behind this story, there’s some beautiful maths waiting to be discovered. It is called Modular Arithmetic. The good thing is that everyone can understand it…well…maybe it is better to say that everyone already knows it! The answer is in the clock.

The clock

Everyone knows what a clock is. If now it’s 9 a.m. and someone tells that you have a meeting in 2 hours, you’ll immediately understand that your meeting is at 11 a.m.. That’s right! And the reason si that 9+2=11. But, if someone tells that your meeting is in 4 hours, you’ll immediately understand that your meeting is at 1 p.m.. However, 9+4=13, not 1. This seems funny but it’s not!

What are we doing? We are restricting our number set! We are not deleting useless numbers but only collecting them into groups of numbers. So, some of them will coincide, as 13 and 1 for example. This relation is called congruence.

So, for examples with small numbers it’s easy, but for ones with big numbers? If now it’s 5, in 1000000 hours, what time is it?

Here’s the problem…this is not so intuitive…so? No problem, Maths is coming to save us!

We can easily identify 1 with 13, 2 with 14, 3 with 15 and so on. But what’s the relationship? Simple, if you divide 14 by 12, the remainder is 2…if you divide 15 by 12, the remainder is 3…and so on. So we identify all the numbers with the same remainder in the division by 12. So the question “If now it’s 5, in 100000 hours, what time will it be?” now has an answer!

We consider 1000000 and we add 5. We obtain 1000005 that is 9+12*83333. So the remainder of the division by 12 is 9. It will be 9.

Snow White’s clock

Now, let’s imagine that there exist clock with an arbitrary number of hours. Let n be this number. In this strange world with n-hour-clocks making calculations is different but not so much.

If it’s 0 now, after x hours, what time will it be? We should divide by n and look at the remainder. This will tell what time it is. Amazing, isn’t it?

Let us now give names to things. The numbers a and b are congruent modulo n if the remainders of the divisions by n are the same. I write a≅b(modn)a≅b(modn).

So, two numbers a and b are congruent modulo n if, starting from the 0, after a or b hours, the question “what time will it be?” has the same answer.

This kind of Arithmetic is useful in many cases. It has plenty of applications in pure mathematics (primality tests, Chinese Remainder Theorem, divisibility rules,…) and in applied mathematics (cryptography).

I’m not going to talk about these things now, but I’ll do it in the future!

Chinese soldiers

You now have this brand-new formalism and you can reformulate Snow White’s problem. She wants a number m that is congruent to 1 modulo 2,3,4,5 and 6 and that is congruent to 0 modulo 7. Easier, isn’t it?

But…we haven’t solved it yet…to do this, let’s come back to an ancient past.

Long long time ago, many years before Christ, Chinese people knew about Modular Arithmetic! They used it to count people, especially soldiers!

I’m not talking of small numbers of soldiers but of a land full of people. So, how can you count them?

There’s a smart way to do it. You decide a priori a set of numbers called n1,n2,…,npn1,n2,…,np. Then you ask to soldiers to divide in groups of n1n1 people and you report the remaining number of them (i.e. the remainder). Let us call it a1a1. You see that the number x of soldiers is congruent to a1a1 modulo n1n1.

You do the same with the other numbers and, finally, you obtain the system

x≅a1(modn1)x≅a1(modn1)

x≅a2(modn2)x≅a2(modn2)

⋯⋯

x≅ap(modnp).x≅ap(modnp).

Essentially it’s the same thing Snow White needs to do!

Let’s do a simple example just to explain how it works. Let suppose that the number of soldiers satisfies the simple system:

x≅1(mod2)x≅1(mod2)

x≅2(mod3)x≅2(mod3)

From the first equation I see that x=2N+1x=2N+1, where N is an integer. That’s true because if I divide x by 2, the remainder is 1. Moreover, these are all the numbers with this property.

We substitute x in the second one obtaining 2N+1≅2mod32N+1≅2mod3, that is 2N≅12N≅1.

Multiplying by 2 both sides, we get N≅4N≅2N≅4N≅2 because 4 is congruent to 1 modulo 3. Hence, N=3M+2N=3M+2 for M integer. Substituting again we get x=6M+5x=6M+5. So, x can be a number in the set of the number that are congruent to 5 modulo 6.

The solution to this problem is not unique in principle. Anyway, knowing the upper and lower bounds of the searched number, we can obtain the exact number. For example if someone told us that x lies between 23 and 30, we would have understood that x is 25. This is how experts suppose Chinese people did.