display | more...

What, like arithmetic in modules?

Not exactly. The "modular" part comes from the word modulo (from the Latin meaning "with the measure"). That doesn't explain much, does it? OK, the idea is that we do normal arithmetic with the integers (..., -1, 0, 1, 2, ...) but instead of having a "number line" that stretches to infinity in both directions, we let it wrap around in a circle. It's because of this that modular arithmetic is sometimes called clock arithmetic. So 6 + 7 isn't 13 on a clock, it's 1. Similarly, modulo 5, 4 + 3 = 2.

Alright, so what's it good for?

Well, part of the joy is, most things you can do to a normal equation, you can do to a modular equation. You can add, subtract, multiply and raise to powers. You can even divide, as long as the modulus is prime (see Noether's writeup here for a proof, etc.). However, many quantities simplify greatly in modular form, and this lets us prove many rather nifty things. For example, we can tell that no two square numbers differ by, say 102. How, you say? Well, any number can be written as either 2n or 2n + 1 (it's either even or odd). So let's square these and look at them modulo 4.

(2n)2 = 4n2 = 0 (mod 4)

(2n + 1)2 = 4n2 + 4n + 1 = 1 (mod 4)

So we now see that any square is equal to either 0 or 1 modulo 4. So the difference between two of them must be -1, 0 or 1 modulo 4. But 102 = 4 x 25 + 2 = 2 (mod 4). So 102 can't be the difference of two squares.

This sounds like mathematician "useful", not real useful

Yes, sorry, it does. However, modular arithmetic is a starting point for a huge branch of mathematics called number theory. This is the branch of maths with all those weird problems like Fermat's Last Theorem, the Goldbach Conjecture and the Riemann Hypothesis. However, in recent years, it's become very important in cryptography. Systems like RSA are based on modular arithmetic. In fact, this is the canonical example of a "useful" bit of pure maths. So there you go.


This has been part of the Maths for the masses project

An example of modular arithmetic that is easy to visualise is by imagining two clocks: one analog(ue) and 12-hour, one digital and 24-hour. Easy so far. Now think of what the clocks show at 3:00a.


o
o I o
o I o
o I-- o
o o
o o
o
and
_ _ _
_|.| || |
_|.|_||_|

Not the best ASCII art, but it does the trick. Now imagine 12 hours elapse. The clocks now show


o
o I o
o I o
o I-- o
o o
o o
o
and
_ _ _
||_ .| || |
| _|.|_||_|

Both clocks are showing that 15 hours have elapsed since midnight, but the top clock is also showing that 3 hours have elapsed since midday. In that sense, 15≡3 mod 12. Our base is 12 - 12 hours on a 12-hour clock - and 15:00 is exactly the same as 3:00p. The same idea can be applied to, say, adding X amount of hours to Y o'clock: conventional addition would see the addition of 33 hours to 4:00a become 37:00, but that just isn't the case. 33 hours after 4:00a is actually 1:00p the next day. Hence 37≡1 mod 12.

The easiest way to calculate if two numbers are congruent modulo n (n being the base) is to divide them both by n and check if the remainders are the same. In other words, for A≡B mod C, then A/C = (B/C)+D, where D is an integer (...-1, 0, 1, 2, 3...).

Exercise: Show that 98 and 54 are congruent modulo 4.
98/4 = 24.5 (24 remainder 2)
54/4 = 13.5 (13 remainder 2)
24.5 = 13.5 + 11
Since 11 is an integer, 98≡54 mod 4

You could easily skip one step by saying that since the remainders are the same, they are congruent modulo 4.

You can perform simple operations on modular arithmetic statements. By "simple operations" I mean addition, subtraction, and multiplication. If, for example, a1≡b1 mod n, and a2≡b2 mod n, then:

  • (a1+a2)≡(b1+b2) mod n (example: if a1=5, a2=3, b1=11, b2=9, and n=6, then (a1+a2) = 8, (b1+b2) = 20, and the remainders of 8/6 and 20/6 are both 2)
  • (a1-a2)≡(b1-b2) mod n (example: 5-3 = 2 and 11-9 = 2, which are congruent with or without the modulo)
  • (a1a2)≡(b1b2) mod n (example: 5*3 = 15 and 11*9 = 99, both of which have remainders of 3 when divided by 6)

Division does not work for every case; this is easily proven by showing our example again: 5/3, when divided by 6, equals 5/18; 11/9, when divided by 6, equals 11/54. If they were congruent, they would be equal (since they are both lower than 6). It is easy to prove that 5/18 ≠ 11/54. Hence, it does not work for all cases.

More examples and applications of modular arithmetic?

  • Days of the week. Months of the year. Seasons. Since pretty much everything to do with time goes in circles, modular arithmetic could be used for almost anything to do with time.
  • ISBN numbers. To check whether an ISBN-10 number is valid, use the following: if the ISBN digits are a, b, c ... up to j, then (10a + 9b + 8c + ... + 2i + j) ≡0 mod 11, regardless of where the dashes in the ISBN number are.
  • A similar idea applies to CAS Registry numbers in chemistry.
  • As pointed out above, modular arithmetic is useful number theory and cryptography.
  • It can even be used in music. On a standard piano keyboard, one note has the same name as one 12 half-tones above it. (This is assuming that the difference between B and C is one half-tone, and the difference between E and F is also one half-tone.)

Log in or register to write something here or to contact authors.