Table of contents |

2 Applications of Modular Arithmetic 3 Congruent modulo 4 External Resources |

In some programming languages, this operation is written as *a* % *n*.

In terms of the floor function floor(z), the greatest integer less than or equal to z:

Both definitions allow for *x* and *y* to be typed as integers or rational numbers.

Modular arithmetic, first systematically studied by Carl Friedrich Gauss at the end of the eighteenth century, is applied in number theory, abstract algebra, cryptography, and visual and musical art.

The fundamental arithmetic operations performed by most computers are actually modular arithmetic, where the modulus is 2^{b} (*b* being the number of bits of the values being operated on). This comes to light in the compilation programming languages such as C; where for example arithmetic operations on "int" integers are all taken modulo 2^{32}, on most computers.

In music, because of octave and enharmonic equivalency (that is, pitches in a 1/2 or 2/1 ratio are equivalent, and C# is the same as Db), modular arithmetic is used in the consideration of the twelve tone equally tempered scale, especially in twelve tone music. In visual art modular arithmetic can be used to create artistic patterns based on the multiplication and addition tables modulo *n* [1].

We call two integers *a*, *b* **congruent modulo n**, written as

*a*≡*b*(**mod***n*) if their difference*a*−*b*is divisible by*n*, i.e. if*a*−*b*=*kn*for some integer*k*.

Here is an example of the congruence notation.

- 14 ≡ 26 (
**mod**12).

If *a* and *b* are integers, the congruence

*ax*≡*b*(**mod***n*)

This equivalence relation has an important properties which follow immediately from the definition: if

*a*_{1}≡*b*_{1}(**mod***n*) and*a*_{2}≡*b*_{2}(**mod***n*)

*a*_{1}+*a*_{2}≡*b*_{1}+*b*_{2}(**mod***n*)

*a*_{1}*a*_{2}≡*b*_{1}*b*_{2}(**mod***n*).

- [
*a*]_{n}+ [*b*]_{n}= [*a*+*b*]_{n} - [
*a*]_{n}[*b*]_{n}= [*ab*]_{n}

- [8]
_{12}[3]_{12}+ [6]_{12}= [30]_{12}= [6]_{12}.

In the ring of integers, if we consider the equation *ax* ≡ 1 (**mod** *n*), then we see that *a* has a multiplication inverse if and only if *a* and *n* are coprime. Therefore,
**Z**/*n***Z** is a field if and only if *n* is prime. It can be shown that every finite field is an extension of **Z**/*p***Z** for some prime *p*.

An important fact about prime number moduli is Fermat's little theorem: if *p* is a prime number and *a* is any integer, then

*a*≡^{p}*a*(**mod***p*).

*a*^{φ(n)}≡ 1 (**mod***n*),

- Perl arithmetic enhancements -- explains the reasoning behind Perl's
*%*operator - Modular Arithmetic...