**Modular arithmetic**is a modified system of arithmetic for integers, sometimes referred to as 'clock arithmetic', where numbers 'wrap around' after they reach a certain value (the

**modulus**). For example, whilst 8 + 6 equals 14 in conventional arithmetic, in modulo 12 arithmetic the answer is 2, as 2 is the remainder after dividing 14 by the modulus 12.

Table of contents |

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

## Definition of Modulo

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

### Implementation of the 'mod' function

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.

## Applications of Modular Arithmetic

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].

## Congruent modulo

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*.

*a*≡

*b*(

**mod**π) if

*a*−

*b*=

*k*π for some integer

*k*. This idea is developed in full in the context of ring theory below.

Here is an example of the congruence notation.

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

*a*is denoted by [

*a*]

_{n}(or simply [

*a*] if the modulus

*n*is understood.) Other notations include

*a*+

*n*

**Z**or

*a*mod

*n*. The set of all equivalence classes is denoted

**Z**/

*n*

**Z**= { [0]

_{n}, [1]

_{n}, [2]

_{n}, ..., [

*n*-1]

_{n}}.

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

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

*x*if and only if the greatest common divisor (

*a*,

*n*) divides

*b*. The details are recorded in the linear congruence theorem. More complicated simultaneous systems of congruences with different moduli can be solved using the Chinese remainder theorem or the method of successive substitution.

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*).

**Z**/

*n*

**Z**by the following formulae:

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

**Z**/

*n*

**Z**becomes a commutative ring with

*n*elements. For instance, in the ring

**Z**/12

**Z**, we have

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

*R*is a commutative ring, and

*I*is an ideal of

*R*, then the elements

*a*and

*b*of

*R*are

**congruent modulo**if

*I**a*−

*b*is an element of

*I*. As with the ring of integers, this turns out to be an equivalence relation, and addition and multiplication become well-defined operations on the factor ring

*R*/

*I*.

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*).

*n*and any integer

*a*that is relatively prime to

*n*,

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

*n*) denotes Euler's φ function counting the integers between 1 and

*n*that are coprime to

*n*. Euler's theorem is a consequence of the Theorem of Lagrange, applied to the group of units of the ring

**Z**/

*n*

**Z**.

## External Resources

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