Modular Equivalence Rules
Modular Equivalence Rules
Algebra rules for manipulating modular equivalences are listed below.
See also
Key Formula
If a≡b(modn) and c≡d(modn), then:
a+c≡b+d(modn)
a−c≡b−d(modn)
a⋅c≡b⋅d(modn)
ak≡bk(modn)for any positive integer k
Where:
- a,b,c,d = Integers, where a ≡ b (mod n) and c ≡ d (mod n)
- n = The modulus, a positive integer
- k = A positive integer exponent
Worked Example
Problem: Find the remainder when 47 × 63 is divided by 10.
Step 1: Reduce each factor modulo 10.
47≡7(mod10),63≡3(mod10)
Step 2: Apply the multiplication rule: you can multiply the remainders and the congruence is preserved.
47×63≡7×3(mod10)
Step 3: Compute the product of the remainders and reduce mod 10.
7×3=21≡1(mod10)
Answer: The remainder when 47 × 63 is divided by 10 is 1.
Another Example
Problem: Find the remainder when 3⁸ is divided by 5.
Step 1: Start by computing a small power. Note that 3² = 9, and reduce mod 5.
32=9≡4(mod5)
Step 2: Use the power rule: square both sides of the congruence to get 3⁴.
34≡42=16≡1(mod5)
Step 3: Square both sides again to get 3⁸.
38≡12=1(mod5)
Answer: The remainder when 3⁸ is divided by 5 is 1.
Frequently Asked Questions
Can you divide both sides of a modular congruence?
Not in general. Division is only valid when the divisor and the modulus are coprime (share no common factor other than 1). For example, from 6 ≡ 12 (mod 6), dividing both sides by 3 gives 2 ≡ 4 (mod 6), which is false. If gcd(c, n) = 1, you can divide both sides by c, because c has a modular inverse mod n.
Why can you replace a number with its remainder in modular arithmetic?
Because any integer a can be written as a = qn + r, where r is the remainder. This means a ≡ r (mod n). The equivalence rules guarantee that substituting r for a in additions, subtractions, and multiplications preserves the congruence, so you get the same final remainder either way.
Modular equivalence rules vs. Properties of equality
Properties of equality (like adding the same value to both sides of an equation) apply to exact numerical equality. Modular equivalence rules are analogous but apply to congruences mod n. A key difference is that division works freely with equality (when the divisor is nonzero) but requires extra conditions in modular arithmetic — the divisor must be coprime to the modulus.
Why It Matters
These rules are the foundation of modular arithmetic, which appears throughout number theory, cryptography (such as RSA encryption), computer science (hash functions, checksums), and competition mathematics. They let you break enormous calculations into small, manageable pieces by reducing at every step. Without these rules, computing something like the last digit of 7¹⁰⁰ would require multiplying out the full number.
Common Mistakes
Mistake: Dividing both sides of a congruence without checking that the divisor is coprime to the modulus.
Correction: Division in modular arithmetic is only valid when gcd(divisor, modulus) = 1. Otherwise the congruence may become false. Use the modular inverse of the divisor instead, or factor out common divisors carefully.
Mistake: Assuming the rules work for exponents in the modulus position, e.g., thinking a^c ≡ a^d (mod n) just because c ≡ d (mod n).
Correction: The power rule lets you replace the base, not the exponent. Replacing the exponent requires a different result (such as Fermat's Little Theorem or Euler's theorem), not the basic equivalence rules.
Related Terms
- Algebra — Broader framework of symbolic manipulation rules
- Properties of Equality — Analogous rules for standard equations
- Equivalence Relation — Congruence mod n is an equivalence relation
- Modular Arithmetic — The arithmetic system these rules govern
- Greatest Common Divisor — Determines when modular division is valid
- Congruence — The relation that these rules preserve
- Modular Inverse — Used for division in modular arithmetic