Modular arithmetic

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 1 Definition of Modulo 1.1 Implementation of the 'mod' function 2 Applications of Modular Arithmetic 3 Congruent modulo 4 External Resources

Definition of Modulo

If a is any integer and n is a positive integer, we write a mod n for the remainder in {0, ..., n-1} that occurs if a is divided by n. For instance, 26 mod 12 = 2.

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

Implementation of the 'mod' function

In practice x mod y can be calculated by using equations, in terms of other functions. Differences arise according to the scope of the variables, which in common implementations is broader than in the definition just given.

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

x mod y = x - y*floor(x/y).

In terms of truncation to the integer part (known as remain() on several calculators and always positive; performed by C's built-in % operator):

x mod y = x - y*iPart(x/y)

In the case of floor, a negative divisor results in a negative modulus (for example, under this definition, 1 mod -2 = -1). The resulting function is what is known as mod() on calculators and is implemented in some high-level languages, including Perl. Perl also uses the % operator to indicate a modulus operation, alluding to the / division operator.

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

The expression x mod 0 is undefined in the majority of numerical systems, although some do define it to be x.

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 and cryptography.

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³², on most computers.

Congruent modulo

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

a = b (mod n)

iff one of the following equivalent conditions holds:

1. their difference is divisible by n;
2. they leave the same remainder when divided by n, i.e. if a mod n = b mod n;
3. a-b=kn for some integer k; (Using this definition, we can generalize to other number systems. For instance, we can define a = b (mod π) if a-b=kπ for some integer k.)
4. a-b ∈ nZ, the ideal of all integers divisible by n.

For instance

14 = 26 (mod 12).

This is an equivalence relation, and the equivalence class of the integer a is denoted by [a]_n (or a + nZ or a mod n, even though the latter notation is ambiguous). This equivalence relation has an important additional property: if

a₁ = b₁ (mod n)    and    a₂ = b₂ (mod n)

then

a₁ + a₂ = b₁ + b₂ (mod n)

and

a₁a₂ = b₁b₂ (mod n).

This can also be expressed as

(a₁ + a₂) mod n = ((a₁ mod n) + (a₂ mod n)) mod n

and

(a₁a₂) mod n = ((a₁ mod n)(a₂ mod n)) mod n

This allows to define an addition and multiplication on the set

Z_n = { [0]_n, [1]_n, [2]_n, ..., [n-1]_n }

of all equivalence classes by the following rules:

• [a]_n + [b]_n = [a + b]_n
• [a]_n × [b]_n = [ab]_n

In this way, Z_n becomes a commutative ring with n elements. For instance, in the ring Z₁₂, we have

[8]₁₂×[3]₁₂ + [6]₁₂ = [6]₁₂.

The term "ring" originates here, because the numbers 0, ..., n-1 are most conveniently arranged in a ring akin to the numbers on the face of a clock.

In abstract algebra, it is realized that modulo arithmetic is a special case of forming the factor ring of a ring modulo an ideal. From the last of the four equivalent conditions, Z_n is indeed the factor ring of Z by the ideal nZ, and so it is often written as Z/nZ.

If a and b are integers, the congruence

ax = b (mod n)

has a solution x if and only if the greatest common divisor gcd(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.

Take b=1. The above statement is equivalent to saying that the units (invertible elements) of the ring Z_n are precisely the elements [a]_n where a and n don't have any non-trivial divisors in common (are "relatively prime"). Therefore, Z_n is a field if and only if n is a prime number. All finite fields are extensions of these.

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

This was generalized by Euler: for any positive integer n and any integer a that is relatively prime to n,

a^φ(n) = 1 (mod n),

where φ(n) denotes Euler's φ function counting the integers between 1 and n that are relatively prime to n. Euler's theorem is a consequence of the Theorem of Lagrange, applied to the group of units of the ring Z_n.

External Resources

• Perl arithmetic enhancements (http://archive.develooper.com/perl6-internals@perl.org/msg05492) -- explains the reasoning behind Perl's % operator