Fun with modular arithmetic

The basic concept of the modulo operation is quite simple. Given two numbers, a and n, a modulo n is the remainder of the division (a/n). Some examples:
6 mod 4 = 2
21 mod 5 = 1
10 mod 2 = 0
Such a simple concept. But you can do beautiful things with it.

In some uses outside of computing, you can begin to think of modulo as less of an operation and more of a class of numbers. We introduce the concept of congruency:
Two integers a and b are said to be congruent in modulo n if (a - b) is a multiple of n. That is, there exists some integer k such that,
a - b = kn

The symbol for congruence is three horizontal lines (≡) [which is 240 in the extended Ascii system]
a ≡ b (mod n)
Congruency is an equivalence relation. It is similar to equals sign, except that many values can be congruent to the same b (mod n). For example,
6 ≡ 1 (mod 5)
21 ≡ 1 (mod 5)
-4 ≡ 1 (mod 5)
Notice how each of these values can be "reduced" to 1. In fact, any value can be reduced to a number ranging between 0 and (n-1). The set of numbers that can be reduced to a specific, unique number between 0 and (n-1) is called an equivalence class. We call the reduced numbers class representatives. To get a list of numbers in each equivalence class, we add or subtract multiples of n from the class representative. For example, a list of values in the class represented by 3 (mod 5) is:
3 + 5 = 8
3 + 2*5 = 13
3 - 5 = -2
3 - 2*5 = -7

{... -12, -7, -2, 3, 8, 13, 18, 23, ...}

Modular arithmetic is very important to cryptography, as are prime numbers and some other related concepts. I'm not going to go into much more detail here because you could write a book on modulo (and more knowledgeable people certainly have!), prime numbers and greatest common divisors, but here's a cute trick for calculating certain mod values. It's a result of two things: the first is that any number in mod n arithmetic can be reduced to its class representative. The second is Lagrange's theorem. The theorem itself seems a bit complicated, but it's implication to modular arithmetic is elegant and simple.

Any integer can be written as a polynomial. The integer 24563 is actually representative of the value (this may look familiar if you know anything about bases)
2x104 + 4x103 + 5x102 + 6x101 + 3x100

The implication of Lagrange's theorem is that those 10s can be reduced to their class representative (or another value that they are congruent to). There are several values that are really easy to work with because of this. For example, use any n such that 10 ≡ 0 (mod n), resulting in a polynomial that looks like this:
24563 = 2x104 + 4x103 + 5x102 + 6x101 + 3x100
≡ 2x04 + 4x03 + 5x02 + 6x01 + 3x00 (mod n)
≡ 2x0 + 4x0 + 5x0 + 6x0 + 3x1 (mod n)
≡ 3 (mod n)
In the above example, some values of n that work are 2, 5 and 10. So, since all the other digits get canceled out by the zero, the only digit that matters when trying to determine the congruence of a value in mod 2, 5 or 10 is the last one.
834974864639 ≡ 9 ≡ 1 (mod 2)
100036342 ≡ 2 (mod 10)
884833636416 ≡ 6 ≡ 1 (mod 5)

Another special value is 9. In mod 9, 10 ≡ 1. We can therefore replace all the 10s in the polynomial with one's:
24563 = 2x104 + 4x103 + 5x102 + 6x101 + 3x100
≡ 2x14 + 4x13 + 5x12 + 6x11 + 3x10 (mod 9)
≡ 2x1 + 4x1 + 5x1 + 6x1 + 3x1 (mod 9)
≡ 2 + 4 + 5 + 6 + 3 (mod 9)
So all we have to do is add up the digits. Not only that, but even the process of adding the digits is affected by the modular arithmetic. Every time our running sum reaches 9, we can replace 9 with 0 and "roll over" to start again:
2 + 4 ≡ 6 (mod 9)
6 + 5 ≡ 9 + 2 ≡ 2 (mod 9)
2 + 6 ≡ 8 (mod 9)
8 + 3 ≡ 9 + 2 ≡ 2 (mod 9)
:. 24563 ≡ 2 (mod 9)

Something similar happens mod 11. In mod 11, 10 ≡ -1. The same thing happens as with 9, but the sign of the value alternates:
24563 = 2x104 + 4x103 + 5x102 + 6x101 + 3x100
≡ 2x-14 + 4x-13 + 5x-12 + 6x-11 + 3x-10 (mod 11)
(odd places become negative, even places are positive)
≡ 2x1 + 4x(-1) + 5x1 + 6x(-1) + 3x1 (mod 11)
≡ 2 - 4 + 5 - 6 + 3 (mod 11)
≡ 0 (mod 11)
And of course, if you need to, you can roll over to zero every time you reach 11.

This theorem makes mental modular arithmetic very, very easy. It's a cute little trick!

0 things about

Fun with modular arithmetic

Post a Comment

Copyright 2012 Phile not Found. See About
Powered by Blogger

"Whenever you find that you are on the side of the majority, it is time to pause and reflect."