|
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.
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 2b (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 232, on most computers.
We call two integers a, b congruent modulo n, written as
For instance
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, Zn 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
Take b=1. The above statement is equivalent to saying that the units (invertible elements) of the ring Zn are precisely the elements [a]n where a and n don't have any non-trivial divisors in common (are "relatively prime"). Therefore, Zn 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
Search Encyclopedia
|
Featured Article
|