Technically:
  • 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.

For any positive integer $n,$ the integers between 0 and $n$ and that are co-prime to $n$ form a group with the usual multiplication. Each element has an inverse which can be computed using the Euclidean Algorithm. This is the basis 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.

CancellingFractions
CommonFactor
Euclid
PierreDeFermat 		(none) BirthdayProblem
MathematicsTaxonomy
PascalsTriangle
Permutation
ZeroFactorial
↓
↓
↓
↓
EuclideanAlgorithm
FermatsLittleTheorem 		Factorial
↓
⇌

You are here

ModuloArithmetic
↓
Integer
↓
↓
↓
↓
ContinuedFraction
Divisor
Euclid
Euler
FermatsLastTheorem
HighestCommonFactor
PrimeNumber
SquareRoot 		(none) RealNumber

Local neighbourhood - D3

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