modular arithmetic (idea)

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, a₁≡b₁ mod n, and a₂≡b₂ mod n, then:

• (a₁+a₂)≡(b₁+b₂) mod n (example: if a₁=5, a₂=3, b₁=11, b₂=9, and n=6, then (a₁+a₂) = 8, (b₁+b₂) = 20, and the remainders of 8/6 and 20/6 are both 2)
• (a₁-a₂)≡(b₁-b₂) mod n (example: 5-3 = 2 and 11-9 = 2, which are congruent with or without the modulo)
• (a₁a₂)≡(b₁b₂) 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.)