## 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.