# Modular Arithmetic and how it works

As children, we grew up learning how to count to 10. Why 10? Well this could be easily justified using the fact that we as humans have 10 fingers and any whole number up to 10 could be easily represented by a quick show of fingers. But what happened when we, as children with this new found power of counting objects up to 10, encountered a number greater than 10? Did we take off our shoes and start counting with our toes? That might have solved the issue for numbers greater than 10 but less than 20 (assuming you aren’t polydactylic) but in all reality, we needed a way to transcend the idea of representing objects with our fingers and/or toes and represent any number, no matter how large.

How did we do this? By using a Place Value system with a base 10. “Place Value” means that using a limited number of symbols, we can represent any number by using these symbols in a variety of combinations. The value of each symbol is based on the position or “place” where the symbol is located in the sequence of symbols.

For example, pick a base. The very first column or “place” should be used for all the symbols preceding the base until the base itself is reached. This is called the “units” place or informally as the “ones” place. This place is usually the farthest left or right place in a sequence. For instructional purposes and for familiarity, we will place the units place on the far right of the sequence.

Once the base has been reached, a second place will be added to the left indicating how many “bases” have been reached. When the amount of “bases reached” has reached the base amount, then a new place is added, again to the left, indicating how many bases of bases have been reached and so on and so forth.

For example, our familiar base 10 system works as follows:

_____ . . . _____ _____ _____ _____

A comma is added after every 3 digits for practical purposes to easily differentiate places in more complex combinations of numbers.

Now let’s go back 4,000 years ago to Sumer, a region of Mesopotamia, (modern-day Iraq). There, children learned to count, but using 60 as a base. Why 60? Did the children of that time have 60 fingers and/or toes? Probably not. The reason for using this number as a base has not been explicitly recorded but there are two convincing hypothesis on why a base 60 number system developed.

One idea, is that instead of using their whole finger to represent a single number, the Babylonians actually counted the 12 knuckles of the four fingers on one hand, using the thumb as a “pointer” and the five fingers on the other as multiples of twelve. So on one hand they had 1-12 and on the other they had how many 12’s, for a total of 12 x 5 = 60.

The other idea is that the number 60 has many divisors, 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, and 60. In fact, 60 is the smallest number divisible by all integers from 1 to 6. This could prove very useful by being able to do division using more whole numbers and resulting in less fractions.

Base 60 is still used in many aspects of our lives today such as the 60 seconds in a minute and the 60 minutes in an hour. The circles is traditionally divided into which are also subdivided into 60 minutes of arc and further divided into 60 seconds of arc.

Modular Arithmetic

Now that we have a brief overview about bases, we can apply the power of Modular Arithmetic to change counting bases. Modular Arithmetic is a very handy and useful tool in mathematics invented by the famous Mathematician Carl Friedrich Gauss in 1801. We know that the number line is infinitely long but if we were to wrap this infinitely long number line around a circle of a given circumference n, we would notice that numbers would “line up” or over lap around the circle. This is the idea behind modular arithmetic. Keep in mind that we are dealing with integers here and not the real numbers.

So the number indicating how large the circle is n, is called the modulus. And we say that after one wrap around, any numbers that line up are congruent. In mathematical terms, when a number a, leaves the same remainder as a number b, we say a and b are congruent written

a ≡ b mod n

The “mod n” part is just notation letting us know that we are in mod n and is not actually part of the equation, per se. However, when the context is understood, it should be OK to omit writing this every time.

In general, any modulo n has n residue classes, one for each integer from 0 to n-1.

Let’s use the timer on your microwave as an example of a base. So we will have n residue classes from the integers 0 to 59.

0, 1, 2, 3, … 56, 57, 58 59

We call this modulo 60 or mod 60 for short. When we add 1 to 59, we return to 0. This is true for any modulus, even our own familiar base 10 (when we add 1 to 9, we return to 0) or even every day objects like traffic lights (Red, Green, Yellow, Red, …). The integers from 0 to 59 in our base 60 example are called Residue Classes.

Now for a quick example, when I was in the military, we would tell time using the 24-hour clock. This is different than the usual 12 hour clock where all 24 hours are represented twice and distinguished using A.M. or P.M.

So when I would get asked what time I would be ready to get picked on Friday for the weekend, I would reply 1600. Of course this did not make sense to most people because the face of a clock only has the numbers 1-12 listed on it. How could I explain correctly to them what time to pick me up so as to maximize our time together on the sunny beaches of San Diego? Using modular arithmetic of course!

Numbers are said to be congruent if their difference is divisible by the modulus. Or stated more succinctly, a is congruent to b if a-b is divisible by n shown algebraically

a ≡ b mod n if a-b / kn for some k

This basically means that the difference must be divisible by the base.

In our example, let’s show that 1600 is congruent to 4:00. For lingo purposes, just think of the colon as “hundred hours” to be in step with 1600. 1600 – 400 is 1200, a multiple of 12. Written

1600 ≡ 400 mod 1200

1600-400 /1200

“So 4:00 P.M. civilian. Don’t be late.”

Another cool example of things you can do with modular arithmetic is calculate the last digit or remainder of a huge number like . Try doing that by hand! Here is how we would do it mod 10.

1919 ≡ 919; (because 19 is congruent to 9 mod 10)

(92)9*9 ≡ (81)9*9 ;

(1)9*9 ≡ 9; (because 81 is congruent to 1 mod 10)

References:

Use of base 60 using hands

Base 60 as a base

http://www.storyofmathematics.com/sumerian.html

Sub-divisions of angles into minutes and seconds

http://en.wikipedia.org/wiki/Minute_of_arc

Modular Arithmetic

http://en.wikipedia.org/wiki/Modular_arithmetic

# Math Tricks and Fermat’s Little Theorem

So you think you’re a math whiz. You storm into parties armed with math’s most flamboyant tricks. You can recite the digits of π and e to 50 digits—whether in base 10 or 12. You can calculate squares with ease, since you’ve mastered the difference of squares x2 – y2 = (x + y)(x – y). In tackling 572, simply notice that 572 – 72 = (57 + 7)(57 – 7) = 64*50 = 3200. Adding 72 to both sides gives 572 = 3249. Image by Hashir Milhan from
Wikimedia Commons under
Creative Commons.

You can also approximate square roots using the truncated Taylor series x ≈ c + (x – c2)/(2c) where c2 is the closest perfect square less than or equal to x. So √17 ≈ 4 + (17 – 16)/(2*4) = 4.125, whereas √17 = 4.123105 . . ..

But do you know what number theory is? It’s not taught in high school, and everyone’s repertoire of math tricks needs some number theory. Mastering modular arithmetic—the first step in number theory—will make you the life of the party. Calculating 83 mod 7 just means find the remainder after dividing by 7: 83 = 11*7 + 6, so 83 ≡ 6 mod 7. But it’s actually easier since 83 = 7*12 + (-1), so 83 ≡ -1 ≡ 6 mod 7. Modular arithmetic reveals the secrets of divisibility. Everybody knows the trick to see whether 3 divides a number; you just add the digits and check if 3 divides that number. But the reasoning is obvious when you write m = 10nan + 10n-1an-1 + . . . + 10a1 + a0 where the ai are the digits of m. Each 10k has a remainder of 1 modulo 3 so man + an-1 + . . . + a1 + a0 mod 3. Using this method generates tricks for other integers.

For instance, if 13 divides m, then 13 divides a0 – 3a1 – 4a2a3 + 3a4 + 4a5 + a6 – 3a7 – 4a+ . . . and the pattern continues. This is because

10 ≡ -3 mod 13,

102 ≡ 10*10 ≡ (-3)(-3) ≡ 9 ≡ -4 mod 13,

103 ≡ 102*10 ≡ (-4)(-3) ≡ 12 ≡ -1 mod 13,

104 ≡ 103*10 ≡ (-1)*(-3) ≡ 3 mod 13,

105 ≡ 104*10 ≡ 3*(-3) ≡ -9 ≡ 4 mod 13,

and 106 ≡ 105*10 ≡ 4*(-3) ≡ -12 ≡ 1 mod 13.

From 106 and onwards the pattern repeats. In fact, calculating 10n mod k for successive n will reveal the divisibility rule for k.

Then comes Fermat’s little theorem, the key to solving seemingly impossible calculations. Fermat. Image from Wikimedia
Commons. Under public domain.

The theorem states for a prime p and integer a that aa mod p. If p doesn’t divide a, then  ap -1 ≡ 1 mod p. I’ll illustrate the power of this little result in a computation. Let’s find 2371 mod 5. We’ll be using 24 ≡ 1 mod 5, which we get from Fermat’s little theorem. Now 2371 = 236823 =(24)9223, so by the theorem, 2371 = (24)9223 ≡ 19223 ≡ 1*23 ≡ 8 ≡ 3 mod 5. Exploiting Fermat’s little theorem can impress your friends, but try to avoid questions. Computing residues modulo a composite number—calculating b mod n for a composite number n—may require paper and ruin the magic.

Leonhard Euler proved a more general version of Fermat’s little theorem; it’s called the Euler-Fermat theorem. This theorem isn’t for parties; explaining it to the non-mathematically inclined will always require paper and some time. Nonetheless, it will impress at dinner if you have a napkin and pen.

Understanding this theorem requires Euler’s totient function φ(n). Euler. From Wikimedia
Commons. Under public domain.

The number φ(n) for some n is the number of positive integers coprime with n that are less than or equal to n. Two numbers a and b are coprime if their greatest common factor is one. Hence 14 and 3 are coprime because their biggest shared factor is 1, but 21 and 14 aren’t coprime because they have a common divisor of 7. Moreover, φ(14) = 6 because 14 has six numbers less than or equal to it that are coprime with it: 1, 3, 5, 9, 11, and 13. Notice that if p is prime, φ(p) = p – 1 because every number less than p is coprime with p.

Now the Euler-Fermat theorem states that aφ(n) ≡ 1 mod n, which looks similar to ap -1 ≡ 1 mod p for a prime p. In fact, if = φ(p) = p – 1 for a prime p, the theorem reduces to Fermat’s little theorem.

Fermat’s little theorem has another generalization, Lagrange’s theorem. Joseph-Louis Lagrange was Euler’s student. Lagrange’s theorem generalizes both the previous theorems and doesn’t even require numbers. But due to the required background in group theory, I won’t go over the theorem. You can find links to more information on Lagrange’s theorem below.

Remember, a math whiz doesn’t need props like a magician does. Hook your audience with some modular arithmetic, and reel the people in with Fermat’s little theorem. If you want to get complicated, the most you’ll need is a pen and some paper.

Sources and cool stuff:

Modular arithmetic: http://nrich.maths.org/4350

Proof of Fermat’s little theorem: https://primes.utm.edu/notes/proofs/FermatsLittleTheorem.html

Euler-Fermat theorem and its proof: http://www.artofproblemsolving.com/Wiki/index.php/Euler%27s_Totient_Theorem

Lagrange’s theorem (only for the brave): http://cims.nyu.edu/~kiryl/teaching/aa/les102903.pdf

Number theory textbooks: Gordan Savin’s Numbers, Groups, and Cryptography and George E. Andrews’s Number Theory

Interesting sources of math tricks and problems: Paul Zeitz’s The Art, Craft of Problem Solving and The USSR Olympiad Problem Book, and What is Mathematics by Richard Courant and Herbert Robbins

# Cryptography: A modern use for modular arithmetic

The common analogy used to describe modular arithmetic is fairly simple. All one has to do is look at an analog clock. For example, if it’s 11 AM and you want to know what time it will be in four hours, we instinctively know the answer is 3 PM. This is modular arithmetic, i.e. 11+4 = 3 mod 12. This is an important concept in the technology driven world we live in. Any time a product is purchased on the internet, cryptography comes into play. The remainder of this paper (pun most definitely intended) will describe how ancient modular arithmetic plays a very important role in today’s society.

History of modular arithmetic

The first known publication of modular arithmetic was in the 3rd century B.C.E, in the book Elements, written by Euclid. Within his book, he not only formalized the fundamentals of arithmetic, but also proved it. In what is known as Euclids Lemma, he states that if a prime number divides the product of two different numbers (x and y), then the prime number must also divide one of the numbers (either x or y), but it could also be both. Between the 3rd and 5th centuries a paper publish by Sun Tzu describes a modular arithmetic process known as the Chinese remainder theorem. This theorem is essentially the basis for modern RSA encryption schemes that are present on every banking/e-commerce website. It uses a congruent set of keys to produce the same numerical value. Imagine if there was a lock on a door that two differently cut keys could unlock and open, this is essentially how Chinese remainder theorem works.

Modern modular arithmetic Oil painting of mathematician and philosopher Carl Friedrich Gauss by G. Biermann (1824-1908). Public Domain.

The modular arithmetic that we use today was discovered by Carl Friedrich Gauss in 1801.

Gauss is famous for numerous discoveries across a wide variety of fields in science and mathematics. Gauss’s proposition, from his book Disquisitiones Arithmeticae, defines modular arithmetic by saying that any integer N belongs to a single residue-class when divided by a number M. The residue-class is represented by the remainder, which can be from 0 to M-1. The remainder is obtained by dividing N by M. Given this fact, Gauss notices that two numbers that differ by a multiple of M are in the same residue-class. He then discusses the role of negative numbers in modular arithmetic. The following is an excerpt from his book:

“The modulus m is usually positive, but there’s no great difficulty in allowing negative moduli  (classes modulo m and -m are the same).  For a zero modulus, there would be infinitely many residue classes, each containing only one element.  [This need not be disallowed.]”

Modular Arithmetic’s Role Today

RSA encryption is named after those who invented it, Ron Rivest, Adi Shamir, and Leonard Adleman (RSA is obtained from their last names). RSA is the process by which information can be passed between two parties without another individual being able to intercept the message. Burt Kaliski has been one of the major contributors to RSA encryption since the 1980’s. I would like to start off with a passage from Burt Kaliski’s paper titled “The Mathematics of the RSA Public-Key Cryptosystem”:

“Sensitive data exchanged between a user and a Web site needs to be encrypted to prevent it from being disclosed to or modified by unauthorized parties. The encryption must be done in such a way that decryption is only possible with knowledge of a secret decryption key. The decryption key should only be known by authorized parties.”

This is a high level description of how RSA encryption works. It is also called public-key encryption, because anyone can obtain a copy of the encryption key it is publically available, but the decryption key cannot be obtained. This makes RSA encryption a secure way of passing data between an individual and a web site.

Performing this calculation (encrypting and decrypting text) is fairly simple. With a basic understanding of modular arithmetic it can be accomplished. First a public and private key must be produced by following the steps below:

1. Generate large prime numbers, p and q (these should be hundreds of digits)
2. Compute the modulus n, n = p×q
3. Compute the totient, totient = (p-1)×(q-1)
4. Choose an “e” > 1 that is co-prime to the totient
5. Choose a “d” such that d×e = 1 mod totient

Once those steps have been completed, a public key (n, e) and a private key (n, d) have been generated. The public key can be distributed to anyone, but the private key must be kept safe. It’s easy to see that without the modular arithmetic this algorithm would be easy to discern. One could generate pairs of random numbers until a pair is found that when multiplied together, would equal the modulus n found in step two above. From there, it would be easy to find all numbers co-prime to the totient in step three. Modular arithmetic then comes into play, because it allows infinite pairs of numbers to satisfy the constraint listed in step five, but it would not allow the user to decrypt the message. In other words, 11+4 = 3 mod 12, but also 11+16 = 3 mod 12. This makes it impossible to determine what the original number was (it could be 4 or it could be 16, or any other multiple of 12).

Once the keys have been generated it is easy to encrypt and decrypt text. To encrypt a message “m,” given the public key (n,e) generated above:

C = me mod n

“C” is then the encrypted message that gets passed to the other party.

To decrypt the message “C” created above, all that is required is the inverse of the operation to encrypt:

M = cd mod n

Let’s do an example to illustrate the instructions listed above (note: we will be using small prime factors because the math is simpler).

1. Select a p and q that are prime
1. P = 11
2. Q = 3
2. The modulus n is then equal to P×Q = 11×3 = 33
3. Computing the totient to be equal to (p-1)×(q-1) = (11-1)(3-1) = 20
4. To select an “e” we must find a number that is coprime to 20
1. The smallest value that is coprime to 20 is 3 because 3 is the smallest number that cannot divide 20 evenly, so “e” = 3
5. Now we need to find “d”, d=e^(-1) mod [(p-1)×(q-1)]
1. Using the Euclidian Algorithm we get d = 7

Now let’s say we want to encrypt the message “4.” To do this we need to know the public key, which in our case is (n=33, e=3).  All we have to do is compute:

C = 43 mod 33 = 31

We can pass 31 (c=31) along to the website, which will then decrypt it using the private key (33, 7):

M = 317 mod 33 = 4

Our message has been successfully “passed” from one place to another.

Thoughts

Without the work from previous mathematicians, this process would not be possible. Modular arithmetic plays a crucial role in our everyday lives and we don’t even notice it. I think it’s an amazing mathematical concept and provides a deep insight into the world of number theory. Even today there are computers constantly trying to figure out how to factor large prime numbers without success. I don’t know if RSA encryption will stand the test of time, but for now it’s the best we’ve got.

References

http://en.wikipedia.org/wiki/Cryptography#History_of_cryptography_and_cryptanalysis

http://www.britannica.com/EBchecked/topic/920687/modular-arithmetic

http://mathworld.wolfram.com/ChineseRemainderTheorem.html