Modulo Arithmetic

Links to this page
Edit this page
Entry portal
Advice For New Users

  • Two numbers are defined to be "equal (modulo k)" if their difference is a multiple of k.
For example, 53 = 5 (mod 12) because 53-5 is 48, and 48 is a multiple of 12.
  • Hence 5 hours from now the time of day will be the same as 53 hours from now.
Working modulo n forms an equivalence relation between the integers, and we can use the numbers from 0 to n-1 as representatives of the equivalence classes.

The integers modulo n form a group under addition in the obvious way.

The integers that are co-prime to n form a group with the usual multiplication. Each element has an inverse which can be computed using Euclid's Algorithm. This is the foundation of the RSA public-key cryptosystem by using Fermat's Little Theorem.

In Modulo Arithmetic there is a special number, called the modulus, and all calculations are done ignoring multiples of that number.

Consider the days of the week. We know that from a Friday, the sixth day of the week (assuming Sunday is the first) that if we add on three days we get to Monday. That means that adding 6 and 3 gives us not 9, but 2. We can see that this makes sense if we ignore a seven.

We can regard 9 and 2 as being effectively the same thing because their difference is 7, the number of days in the week.

The same thing happens with larger numbers. If we add 20 days to the Friday then that's 6+20=26, but we can "throw away" 21 (which is a whole number of weeks, and a multiple of 7) and get left with 5. That's a Thursday.

Notice also that when we added 20 we got the same answer as subtracting 1. That's because 20+1 gives us 21, which is effectively the same as 0. Thus -1 can be though of as the same as 6, 13, 20, etc.

These numbers are all equal to 6 (modulo 7) because if you divide by 7 they all leave the same remainder - namely, 6.

Modulo Arithmetic is used widely in number theory and cryptography, and plays a crucial role in modern computing and secure communications. It can also be used to simplify many calculations, such as those found on the page that shows how to compute What Day Of The Week a certain date falls on.

Also known as modular arithmetic.

Links to this page / Page history / Last change to this page
Recent changes / Edit this page (with sufficient authority)
All pages / Search / Change password / Logout