In arithmetic, the remainder (or modulus) is the amount "left over" after performing the division of two integers which do not divide evenly (from Wiki).
Modulo operation have a special property, which is of great use to us. Let us study about it in two steps:
Suppose we are given an arithmetic expression with many addition and multiplication operations - for which we want
to know not the result itself, but remainder of division result by some value M:
(A * B + C * D * (E + F)) % M = ?
Such calculation is not hard as long as numbers are small enough and amount of multiplications is not gread. If this condition does not hold, a simple rule could be applied:
Any member of such expression (including intermediate results) could be substituted with remainder left after division it by M, i.e. for example expression above equals to the following:
((A * B) % M + C * (D % M) * (E + F)) % M
Or, let us have an example with numbers (operation ^ denotes raising to power):
(2^10 + 3^5) % 7 = ?
it is equal to:
((2^3)^3 * 2 + (3^2)^2 * 3) % 7
substitute some parts with remainders:
((2^3 % 7)^3 * 2 + (3^2 % 7)^2 * 3) % 7 = ((8 % 7)^3 * 2 + (9 % 7)^2 * 3) % 7 =
= (1^3 * 2 + 2^2 * 3) % 7 = (2 + 12) % 7 = 14 % 7 = 0
You can check this calculating the first expression manually.
Though such usage of remainder could look artificial and not important for everyday needs, it is however widely used when dealing with checksums and cryptography (for the latter all modern methods employ modular arithmetic).
If you want some practice for this rule, please try Modular Calculator Task.
Different numbers which yield the same remainder being divided by given M are called congruent. So we can say
that in arithmetic expression with additions and multiplications we can substitute members by congruent values and
the new result will be congruent to old result.
This term is used in the name of Linear Congruential Generator for random numbers.
"Magic property" described above leads us to the funny experiment.
Let us "invent" special math which uses small set of numbers - only integers from 0 to M-1 instead of infinite
set (including millions, trillins, negative, rational, irrational values etc.) which is commonly used.
For example with M=13 our math will deal with values:
0 1 2 3 4 5 6 7 8 9 10 11 12
It is easy to define operation of addition here - if the sum fall over the upper bound of the set, we just wrap it back with modulo operation:
A + B = (A + B) % M
2 + 3 = 5
5 + 8 = (13 % 13) = 0
7 + 10 = (17 % 13) = 4
Subtraction is simple too: if the result is negative we simply add M to it so wrapping it back around the lower bound:
5 - 3 = 2
0 - 8 = (-8
4 - 7 = (-3 = 13 - 3) = 10
Multiplication is just a repetition application of addition, so it is simple too:
3 * 3 = 9
5 * 5 = (25 % 13) = 12
But what to do about division???
At first, remember that division could be expressed as multiplication with inverse element:
A / B = A * 1/B = A * inv(B)
Where inverse is the value which yields 1 when multiplied by the given value:
inv(X) = Y means that X * Y = 1
Now it is easy to define the same things for our finite set - to divide A/B we need at first to find such a
value X=inv(B) which produces 1 when multiplied by B - and then simply multiply A*X. For example:
3 / 5 = 3 * inv(5) = 3 * 8 = 11
9 / 7 = 9 * inv(7) = 9 * 2 = 5
let us test these results by multiplying divisor and quotient back:
11 * 5 = (55 % 13) = 3
5 * 7 = (35 % 13) = 9
The only tricky question here is how to calculate the inverse itself? Well, please refer to the problem Modular Inverse which explains what programming is necessary for this!
Note 1: of course such "finite math" produces different results for different values of modulo M. Striclty speaking
we have as many such "maths" as there are different positive integers :)
Note 2: with some values of M it could happen that some values do not have an inverse at all! For example
with M=12 all even numbers (2, 4, ..., 10) could not produce 1 by multiplication with any other number.
The criteria for inverse to exist is simple: gcd(X,M) = 1 where gcd denotes
the greatest common divisor for value in question X and modulo of the given math M.
Note 3: These "finite sets" and "finite math" on them are one of the most popular example of more common
Finite Fields (also known as) Galois Fields. Fields of this precise
kind are often specified as Z/MZ where M is the number of elements, e.g. Z/13Z.