Monthly Archives: November 2018

Another week, another Manjul Bhargava delight.

Arithmetic is usually taught in base 10. We have 10 unique symbols (0,1,2,3,4,5,6,7,8,9) and a place value system with the lowest value being , the next being , the next being and so on. So a number like .

So far so good, but you could do this with a different base. Let’s say you used base – 3. That means you would need 3 unique symbols (people usually use 0,1,2, but they could well use ⊕,ψ,◊ if you desired – just convenience, familiarity with the traditional symbols make us use 0,1,2). Then, we use a place value system, just using as the lowest value, as the next value place, followed by and so on.

Next, one generalizes the notion of equality of numbers to something called congruence. For this concept,  we use the symbol, rather than . Two numbers and are equal if they are, well, equal! But, they are congruent, modulo , if they both give the same remainder when divided by . This is written as .

For instance, etc.

The thing most people learn in high school is that the sum and difference (or in general, any linear combination) of two numbers (say ) modulo is just the sum or difference or the same linear combination of and . In equation form, . This is called the distributive law of modulo arithmetic.

An additional property that also is true is that the of two numbers modulo is also the product of each of the two numbers and individually modulo . Again, in equations,

Proving this is easy. If you write as multiples of plus remainders, as below, where are integers in base-10, while are in the range as good remainders should be!

Then the product of these modulo is . The first three terms are all multiples of and we use the distributive law to reduce those “mods” to 0 remainder when divided by . The last term is , which is exactly .

A simple consequence of this is that if you have any number, say with four digits, which can be written as , that is equal to . Now, since or divides and , all we need is to have for the number to be divisible by . Alternatively we need for the number to be divisible by . That’s the origin of a simple high-school mnemonic.

This is the basis of a simple trick.

Consider a number, say . Ask someone to jumble up the digits and subtract the smaller number from the larger number. So, let’s say I get and then compute . Ask the person to hide one of the digits and reveal the others. You can easily guess the hidden digit. The reason is simple – the difference of these two numbers is going to be a multiple of . So the sum of the digits is going to be a multiple of , which allows one to guess the digit. And why is the difference a multiple of ? – Suppose we start with the number and jumble up the digits to get . If we subtract the second from the first, we will get . Each of the bracketed differences is a multiple of , then we just use the product rule discussed above.

This brings us to the card trick discussed a few posts before.

Consider that a sequence of cards is placed face down in two piles, with the cards cut in two. The first pile, top to bottom, is, say of Hearts and the other pile has exactly the same (the other half of the torn cards), but reversed in order, so it would be of hearts. Place the first set of cards next to the second set.

Now, use the following phrases . Break each word wherever you want (say GARD-NER) and as you enunciate every letter (G-A-R-D), move a card on the first pile from the top to the bottom. When the break (at N-E-R as I arbitrarily chose) arrives in the word, switch to the other pile and complete the word there. Do this for the next work and so on. After each word ends, place the top card of each pile in a separate place with each other. These two will be perfectly the cut halves, as in the video in the previous post. Then go on to the next word.

Why does it work?

The word “GARDNER” has letters. That is . So what?

Well, if the initial set of cards looks like

Then if we sequentially move cards to the bottom on the left pile, we have

Why the ? That’s to handle the case where we move more than the full stack of cards (i.e., ).

Next, we move cards to the bottom of the second pile, resulting in

For the top cards to match, we must have

Now, if we chose , then the two sides of the equation are equal. In that case, we just need that the total number of cards moved (in both piles) needs to be , but modulo . Note that the number of letters in is and note that .

The same argument works for the next two words. Since we removed one card, we have , which has letters, which is . And finally, has letters, which is . And the cards magically line up.

Next up – a magical number.