Modulo arithmetic & cards

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 10^0=1, the next being 10^1=10, the next being 10^2=100 and so on. So a number like 145=1 \times 10^2 + 4 \times 10^1 + 5 \times 10^0.

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 3^0=1 as the lowest value, 3^1=3 as the next value place, followed by 3^2 and so on.

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

For instance, 16=1\:  mod \: 3, 17 = 2 \: mod \: 5, ... 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 a, b) modulo N is just the sum or difference or the same linear combination of a \: mod \: N and b \: mod \: N. In equation form, (\alpha \: a + \beta \: b) \: mod \: N = \alpha (a \: mod \: N) + \beta (b \: mod \: N). This is called the distributive law of modulo arithmetic.

An additional property that also is true is that the {\bf product} of two numbers a, b modulo N is also the product of each of the two numbers a and b individually modulo N. Again, in equations,

(a \: b) \: mod \: N = (a \: mod \: N) (b \: mod \: N)

Proving this is easy. If you write a, b as multiples of N plus remainders, as below, where Q_a, Q_b are integers in base-10, while R_a, R_b are in the range 0, 1,2,...(N-1) as good remainders should be!

a = Q_a N + R_a

b = Q_b N + R_b

Then the product of these modulo N is (Q_a Q_b N^2 + Q_a R_b N + Q_b R_a N + R_a R_b) \: mod \: N. The first three terms are all multiples of N and we use the distributive law to reduce those “mods” to 0 remainder when divided by N. The last term is R_a R_b \: mod \: N, which is exactly (a \: mod \: N)(b \: mod \: N).

A simple consequence of this is that if you have any number, say with four digits, which can be written as 1000 a + 100 b + 10 c + d, that is equal to (999a+99b+9c) + (a+b+c+d). Now, since 3 or 9 divides 999,99 and 9, all we need is to have a+b+c+d \: mod \: 3=0 for the number to be divisible by 3. Alternatively we need a+b+c+d \: mod \: 9 =0 for the number to be divisible by 9. That’s the origin of a simple high-school mnemonic.

This is the basis of a simple trick.

Consider a number, say 576281. Ask someone to jumble up the digits and subtract the smaller number from the larger number. So, let’s say I get 156728 and then compute 576281 - 156728 = 419553. 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 9. So the sum of the digits is going to be a multiple of 9, which allows one to guess the digit. And why is the difference a multiple of 9? – Suppose we start with the number 10^6 a + 10^5 b + 10^4 c + 10^3 d + 10^2 e + 10^1 f + g and jumble up the digits to get 10^6 b + 10^5 c + 10^4 e + 10^3 d + 10^2 f + 10^1 g + a. If we subtract the second from the first, we will get a (10^6-1)+b (10^5-10^6) + c (10^4-10^5)+d (0) + e(10^2-10^4)+f(10^1-10^2)+f(1-10^1). Each of the bracketed differences is a multiple of 9, 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 Ace, King, Queen, Jack 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 Jack, Queen, King, Ace of hearts. Place the first set of cards next to the second set.

Now, use the following phrases GARDNER, BHARGAVA, MAGIC. 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 7 letters. That is 3 \: mod \: 4. So what?

Well, if the initial set of cards looks like

0 \: \: \: \: \: \: \: N-1 \\  1 \: \: \: \: \: \: \: N-2 \\  2 \: \: \: \: \: \: \: N-3 \\  . \\  . \\  . \\  N-1 \: \: \: \: \: \: \: 0

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

(m) mod \: N \: \: \: \: \: \: \: \: \: \: \: N-1 \\  (m+1) mod \: N \: \: \: \: \: \: \: N-2 \\  (m+2) mod \: N \: \: \: \: \: \: \: N-3 \\  . \\  . \\  . \\  (m+N-1) mod \: N \: \: \: \: \: \: \: 0 \\

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

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

(m) mod N \: \: \: \: \: \: \: \: \: \: \: (N-(k+1)) mod \: N \\  (m+1) mod N \: \: \: \: \: \: \: (N-(k+2)) mod \: N \\  (m+2) mod N \: \: \: \: \: \: \: (N-(k+3)) mod \: N \\  . \\  . \\  . \\  (m+N-1) mod \: N \: \: \: \: \: \: \: (N-k) mod \: N \\

For the top cards to match, we must have m \: mod \: N= (N-k-1) mod N

Now, if we chose k = N-m-1, 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 m + (N-m-1) = N-1, but modulo N. Note that the number of letters in GARDNER is 7 and note that 7 = 3 \: mod \: 4.

The same argument works for the next two words. Since we removed one card, we have BHARGAVA, which has 8 letters, which is 8 = 2 \: mod \: 3. And finally, MAGIC has 5 letters, which is 1 \: mod \: 2. And the cards magically line up.

Next up – a magical number.

Leave a Reply