Modulo

Given two positive numbers a and n, a modulo n (often abbreviated as a mod n) is the remainder of the Euclidean division of a by n, where a is the dividend and n is the divisor.

[1] For example, the expression "5 mod 2" evaluates to 1, because 5 divided by 2 has a quotient of 2 and a remainder of 1, while "9 mod 3" would evaluate to 0, because 9 divided by 3 has a quotient of 3 and a remainder of 0.

Although typically performed with a and n both being integers, many computing systems now allow other types of numeric operands.

The range of values for an integer modulo operation of n is 0 to n − 1. a mod 1 is always 0.

When exactly one of a or n is negative, the basic definition breaks down, and programming languages differ in how these values are defined.

Computers and calculators have various ways of storing and representing numbers; thus their definition of the modulo operation depends on the programming language or the underlying hardware.

In nearly all computing systems, the quotient q and the remainder r of a divided by n satisfy the following conditions: This still leaves a sign ambiguity if the remainder is non-zero: two possible choices for the remainder occur, one negative and the other positive; that choice determines which of the two consecutive quotients must be used to satisfy equation (1).

In number theory, the positive remainder is always chosen, but in computing, programming languages choose depending on the language and the signs of a or n.[a] Standard Pascal and ALGOL 68, for example, give a positive remainder (or 0) even for negative divisors, and some programming languages, such as C90, leave it to the implementation when either of n or a is negative (see the table under § In programming languages for details).

is the integral part function (rounding toward zero), i.e. the truncation to zero significant digits.

Thus according to equation (1), the remainder has the same sign as the dividend a so can take 2|n| − 1 values: Donald Knuth[3] promotes floored division, for which the quotient is defined by where

Thus according to equation (1), the remainder has the same sign as the divisor n: Raymond T. Boute[4] promotes Euclidean division, for which the quotient is defined by where sgn is the sign function,

, and its sign depends on which side of zero it falls to be within these boundaries: Common Lisp also uses ceiling division, for which the quotient is defined by where ⌈⌉ is the ceiling function (rounding up).

If the dividend is positive and the divisor is negative, then the truncated and Euclidean definitions agree.

If the dividend is negative and the divisor is positive, then the floored and Euclidean definitions agree.

If both the dividend and divisor are negative, then the truncated and floored definitions agree.

As described by Leijen, Boute argues that Euclidean division is superior to the other ones in terms of regularity and useful mathematical properties, although floored division, promoted by Knuth, is also a good definition.

When the result of a modulo operation has the sign of the dividend (truncated definition), it can lead to surprising mistakes.

For example, to test if an integer is odd, one might be inclined to test if the remainder by 2 is equal to 1: But in a language where modulo has the sign of the dividend, that is incorrect, because when n (the dividend) is negative and odd, n mod 2 returns −1, and the function returns false.

For special cases, on some hardware, faster alternatives exist.

For example, the modulo of powers of 2 can alternatively be expressed as a bitwise AND operation (assuming x is a positive integer, or using a non-truncating definition): Examples: In devices and software that implement bitwise operations more efficiently than modulo, these alternative forms can result in faster calculations.

The properties involving multiplication, division, and exponentiation generally require that a and n are integers.

@mod, @rem In addition, many computer systems provide a divmod functionality, which produces the quotient and the remainder at the same time.

There does not seem to be a standard notation for this operation, so let us tentatively use a modd n. We thus have the following definition:[60] x = a modd n just in case d ≤ x ≤ d + n − 1 and x mod n = a mod n. Clearly, the usual modulo operation corresponds to zero offset: a mod n = a mod0 n. The operation of modulo with offset is related to the floor function as follows: To see this, let

The modulo with offset a modd n is implemented in Mathematica as Mod[a, n, d] .

[60] Despite the mathematical elegance of Knuth's floored division and Euclidean division, it is generally much more common to find a truncated division-based modulo in programming languages.

Leijen provides the following algorithms for calculating the two divisions given a truncated integer division:[5] For both cases, the remainder can be calculated independently of the quotient, but not vice versa.

The operations are combined here to save screen space, as the logical branches are the same.