|Application of the Euclidean Algorithm|
Modular Arithmetic is a system of arithmetic in which numbers 'wrap around' upon exceeding a maximum value, so that any arithmetic operation on a finite set of numbers remains within the set.
The most common everyday use of modular arithmetic is timekeeping. Using a standard 12-hour clock, adding 4 hours to a clock at 11:00 set the clock at 3:00, so 11+4 =3 on a clock.
If we wrap around a number n, then numbers that are multiples of n away from each other are said to be congruent 'mod n'. On a clock the numbers wrap around every 12, so we say for example that . Note that if we wrap around every n, we start counting from zero, then when we reach the number n, we return to zero (the number n is not generally used, since it is the same as zero in this system).
We can extend this idea to allow numbers to wrap around at any number we choose. We could also say that since 13 and 27 are a multiple of 7 apart from each other.
Another explanation of modular arithmetic: http://mathworld.wolfram.com/ModularArithmetic.html