Remainder (integer division)

Formal definition

The usual statement of the division algorithm for integers says: given an integer a (the dividend) and a nonzero integer b (the divisor), there exist integers q (quotient) and r (remainder) such that a = bq + r, with 0 ≤ r < |b| when one adopts the nonnegative-remainder convention. Under this convention r is unique for fixed a and b ≠ 0. Other conventions allow r to have different sign ranges, but the basic idea is the same: r measures what remains after subtracting an integral multiple of b from a.

Properties and sign conventions

Key properties and variations include:

• The remainder is strictly smaller in absolute value than the divisor’s absolute value when the nonnegative convention is used.
• For positive divisor b, the standard remainder satisfies 0 ≤ r < b.
• When negative numbers are involved, some conventions require r to be nonnegative, while others let r inherit the sign of the dividend or follow implementation-specific rules; this causes practical differences in computing environments.

Examples and computation

Simple numeric examples make the idea concrete: dividing 17 by 5 gives quotient 3 and remainder 2 because 17 = 5·3 + 2. If the dividend is smaller than the divisor, the quotient is 0 and the remainder equals the dividend (e.g., 3 divided by 10 gives q = 0, r = 3). With negative dividends or divisors the pair (q,r) depends on the chosen convention; the identity a = bq + r remains valid under any consistent choice.

Relation to modular arithmetic and uses

The remainder underlies the modulo operation and modular arithmetic, where numbers are considered equivalent if they have the same remainder when divided by a fixed modulus. This perspective is central in number theory and has many applications: clock arithmetic, hashing, checksums, and algorithms for greatest common divisors and cryptography all use remainders or residues.

Distinctions and notable facts

It is important to distinguish the informal word "remainder" from terms like "modulus" or "residue class" used in abstract algebra: a remainder is a specific representative integer, while a residue class is an equivalence class of many integers sharing the same remainder modulo a given number. Practical computing also treats remainders differently across systems, so one should be explicit about the sign convention or the programming language semantics when using the operation in code or proofs.

For further reading on related concepts see general treatments of arithmetic, algorithmic descriptions of division, properties of integers, and formal definitions of quotient.