Fun With Modular Arithmetic

A reader recently suggested I write about modular arithmetic (aka "taking the remainder"). I hadn't given it much thought, but realized the modulo is extremely powerful: it should be in our mental toolbox next to addition and multiplication.


This is a companion discussion topic for the original entry at http://betterexplained.com/articles/fun-with-modular-arithmetic/

I love this series; it reminds me of everything I’ve forgotten since school.

I think there’s a small error in this entry, though: on clocks, the big hand is usually the minute hand; thus, “in 7 hours”, the big hand will be in exactly the same place it is now. The small hand, though, will have moved.

@Robert: slaps forehead, thank you for that catch! Rather than trying to be clever, I think I’ll just say “hour hand” :).

“3a + 5b = 7… let’s “mod 3 it”: 0 + 2b ≡ 2 mod 3, or b ≡ 1 mod 3”

Shouldn’t it be “0 + 2b = 1” since 7 mod 3 1?

@Mark: Thank you! Another case of me being too clever for my own good… it should be 3a + 5b = 8 to make that equation work. I’ll update the article.

Good post!

In addition to public-key cryptography like Diffie Hellman and RSA, modular operations are very useful in private-key (symmetric-key) algorithms like the Advanced Encryption Standard (AES).

Modular operations are useful there because you can represent a byte as a polynomial with coefficients that are either 1 or 0. Once you do this, you can take advantage of a lot of nice mathematical properties. Instead of dividing by a number, you can divide by a polynomial and things just work out. Logarithms work in a similar way.

I had fun learning about the details and wrote about the details in Act 3 of my stick figure guide to AES.

The modulo operation (abbreviated “mod”, or “%” in many programming languages) is the remainder when dividing. For example, ”5 mod 3 = 2″ which means 2 is the remainder when you divide 5 by 3.

This is what I used to think too, but it’s wrong. It only works this way if both numbers are positive. When either of the numbers is negative, it doesn’t quite work that way.

5 mod 3 = 2

However

-5 mod 3 = 1

That’s because the real definition is that a mod n = b if (a - b) is an integer multiple of n.

5 - 2 = 3 => 5 mod 3 = 2.
(-5) - 1 = 6 = 2 * 3 => -5 mod 3 = 1

This is confusing enough, but the modulo operator in programming languages has behavior that is hard to predict for negative values. (Notice that that article also states, incorrectly, that modulo is the same as remainder.)

If you end up writing an article about negative mods, I would use the “clock math” basis for it. In a problem like a mod n = b, the n is the number of places on the clock. The a is the number of steps you take, with negative being backwards. b is the number you land on.

It’s also possible to have a negative n, but I don’t know what that’s supposed to mean…maybe the clock is made of anti-matter?

'Intuitively, I have a chemical analogy that “evenness” is a molecule some numbers have, and cannot be removed by multiplication.'
How about a genetic analogy? Let’s say that being even is a dominant allele, and being odd is recessive. Whenever a multiplication has at least one dominant allele, the result is even. Only when both multiplicands are odd, is the result odd.

@Yuval: Oh, that’s an interesting analogy too – thanks! :).

[…] […]

[…] […]

a = b (mod n) since the equal sign is often easier to type than the congruent sign that was intended.
Basically, the truth of a = b (mod n) is the same as the truth of mod(a,n) = mod(b,n)

Can anyone answer this question and explain it?

In mod 6, What is 3 divided by 5??

3x^3-16x-1≡AX(x-1)(x+2)+B(x-1)^2+C(4x^2+3)

[…] Fun with Modular Arithmetic: Threeven, Modulo, Clock Math, and Cryptography. This entry was posted in !small, Uncategorized and tagged education, math, modular arithmetic. Bookmark the permalink. ← Twitter Code Swarm Google Buzz and the Abundance of Information About Nothing → […]

Jess, I think I can answer your question. If you want to take 3/5 (mod 6), you just need to rephrase the question a bit. What do we want 3/5 to do? Basically, the answer to “3 divided by 5,” which we often call “three fifths,” has the defining property that if you multiply it by 5 you get 3. So instead of finding 3/5 (mod 6), I’ll find the number that has the property that when I multiply it by 5 (mod 6) I get 3.

What number is this? 3 seems to fit the bill, since 3*5 = 15 = 3 (mod 6). Hence, 3/5 = 3 (mod 6).

There’s another way to understand this in this case only. Since 5 = -1 (mod 6), your question is the same as 3/(-1) (mod 6), which is clearly -3, which is the same as 3 (mod 6).

Hope that helps.

@Dan: Awesome answer, thanks for dropping by!

Brilliant! This article explains everything really clearly and I totally understand mods now!!!

Thx!!!

so…like this?
Find the last digit of 3 to the power of 152.
First we make a chart:

3 to the 1= 3 mod 10.

3 to the 2= 9 mod 10.

3 to the 3= 7 mod 10.

3 to the 4= 1 mod 10.

3 to the 5= 3 mod 10.

        9

        7

        1

We find a pattern of 4 numbers (3, 9, 7, 1) so we divide 152 by 4. It divides in evenly so 1 (the fourth number in the pattern) is the last digit of 3 to the power of 152.

Thanks!

In what modular arithmetics would be true? 1-3=2

Thanks