Skip to main content

Divisibility and Euclidean Remainders

What this concept is​

For integers a and b, a | b means that some integer k satisfies b = ak. It is a relation, not the numerical quotient b/a. For a positive divisor m, Euclidean division represents any integer n uniquely as n = qm + r with 0 ≤ r < m. The quotient q can be negative.

Why it matters here​

A canonical remainder gives a consistent representative for a cyclic position. Negative offsets are common in ring buffers and date calculations; getting the sign convention wrong produces wrong indexes.

Concrete example​

For n = -17 and m = 5, take q = -4, r = 3: -17 = (-4)5 + 3. Taking q=-3 would give r=-2, which violates the stated range. Python's divmod(-17, 5) follows the nonnegative-remainder convention for a positive divisor; other language conventions must be checked.

To see uniqueness, suppose qm+r = q'm+r' with both remainders in range. Then (q-q')m = r'-r. The right side lies strictly between -m and m, so its only possible multiple of m is zero. Thus r=r' and q=q'.

Common confusion / misconception​

Every nonzero integer divides 0 because its multiple by 0 is 0. Under the existential definition, 0 divides only 0; this does not make division by zero a valid arithmetic operation. A negative dividend does not imply a negative canonical remainder.

How to use it​

State the modulus domain first, compute q and r with integer arithmetic and check both the reconstruction and remainder bounds. Do not convert large integers to floating point to obtain a quotient.

Check yourself​

Does 6 divide 42? Does 6 divide 43? Supply a witness for the first and a remainder for the second. Answers: witness 7; remainder 1.

Mini drill or application​

Write canonical quotient/remainder pairs for -23 divided by 7 and 23 divided by 7. Verify each equality and range. Then explain why a range check is necessary even if reconstruction succeeds.

Read this only if stuck​

Source backbone: Mathematics for Computer Science reference. For the freely available original, use MIT’s 2015 Chapter 8 readings. See the reading guide for topic selection; chapter numbering can differ across editions.