Most recent change of ModuloArithmetic

Edit made on February 16, 2009 by GarethMcCaughan at 09:07:55

Deleted text in red / Inserted text in green

[[[>50 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.

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

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.