Modulo Operations: Addition and Multiplication
Modular arithmetic works with equivalence classes. When we select a modulus n, two numbers are considered equivalent if they differ by a multiple of n. Formally, [x] denotes all integers of the form x + n·k where k is any integer.
Addition modulo n combines residues by adding and reducing: (a + b) mod n = ((a mod n) + (b mod n)) mod n.
Multiplication modulo n follows a similar principle: (a × b) mod n = ((a mod n) × (b mod n)) mod n.
These operations behave predictably because they're grounded in the arithmetic of integers—and integer arithmetic has well-understood properties that carry through to the modular case.
Remainder Calculations
Computing remainders correctly is essential for understanding modular properties. Below are the standard formulas for Euclidean division and negative remainders.
r = x − |y| × ⌊x / |y|⌋
r_neg = x − y × ⌈x / y⌉
x = ⌊x / y⌋ × y + r_neg
x— The dividend (number being divided)y— The divisor (number dividing into x)r— The Euclidean remainder (always non-negative)r_neg— The remainder when allowing negative values⌊ ⌋— Floor function (rounds down to nearest integer)⌈ ⌉— Ceiling function (rounds up to nearest integer)
Associativity in Modular Arithmetic
Associativity means the grouping of operations doesn't affect the result. In modular arithmetic, both addition and multiplication are associative.
Modulo addition: ([x] + [y]) + [z] = [x] + ([y] + [z])
Modulo multiplication: ([x] × [y]) × [z] = [x] × ([y] × [z])
This property holds because the underlying integer operations (addition and multiplication) are associative. When we compute ([x] × [y]) × [z], we eventually simplify to [x × y × z] regardless of parentheses placement. Since integer multiplication is associative—(x × y) × z = x × (y × z)—the modular version inherits this property.
Commutativity and Distributivity
Modular arithmetic respects two more fundamental properties.
Commutativity means the order of operands doesn't matter: [x] + [y] = [y] + [x] and [x] × [y] = [y] × [x]. Since addition and multiplication of integers are commutative, their modular counterparts are too.
Distributivity links multiplication and addition: modular multiplication distributes over addition, just as regular multiplication does.
([x] + [y]) × [z] = ([x] × [z]) + ([y] × [z])[x] × ([y] + [z]) = ([x] × [y]) + ([x] × [z])
Again, this follows from the distributive property of integers. Modular arithmetic inherits these properties seamlessly because the modulo operation respects addition and multiplication.
Common Pitfalls in Modular Arithmetic
Understanding the limits and gotchas of modular properties helps avoid computational errors and conceptual confusion.
- Order matters for division — While multiplication and addition are commutative in modular arithmetic, division is <em>not</em>. <code>[x] ÷ [y]</code> may not equal <code>[y] ÷ [x]</code>. In fact, division in modular arithmetic requires a multiplicative inverse, which doesn't always exist. Only when <code>gcd(y, n) = 1</code> can you divide by <code>y</code> modulo <code>n</code>.
- Negative remainders require careful handling — Different definitions of modulo produce different results for negative dividends. The Euclidean definition always gives non-negative remainders, while other conventions allow negatives. When working across systems or programming languages, verify which convention is in use to avoid subtle bugs.
- Distributivity doesn't work for exponentiation — You cannot distribute exponents across modular multiplication: <code>(x × y)^k mod n ≠ (x^k mod n) × (y^k mod n)</code> in general. Instead, use <code>x^k × y^k ≡ (x×y)^k (mod n)</code>, which does follow the rules of modular arithmetic.
- Modulus value changes the property's meaning — The same numbers behave differently under different moduli. For instance, <code>5 mod 3 = 2</code>, but <code>5 mod 7 = 5</code>. Always verify that your modulus choice reflects your problem domain, whether it's cyclic groups in cryptography or clock arithmetic.