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.
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.
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.
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.
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)
[…] 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).
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.