Modular Equivalence

Modular Equivalence

Two integers are equivalent mod n if they leave the same remainder when divided by n.

For example, 5 and 17 are equivalent mod 4 since they both have remainder 1 when divided by 4. We write
5 ≡ 17 (mod 4).

Examples of modular equivalence: 7≡2(mod 5), 7≡3(mod 4); 13≡3(mod 5), 13≡1(mod 4); 4≡4(mod 5), 4≡0(mod 4); 30≡0(mod 5), 30

See also

Modular equivalence rules, modulo n

Key Formula

a \equiv b \pmod{n} \iff n \mid (a - b)

Where:

$a$ = The first integer
$b$ = The second integer
$n$ = The modulus — a positive integer that both a and b are divided by
$n \mid (a - b)$ = n divides (a − b) exactly, meaning (a − b) is a multiple of n

Worked Example

Problem: Determine whether 23 and 53 are equivalent mod 6.

Step 1: Compute the difference of the two integers.

53 - 23 = 30

Step 2: Check whether the modulus n = 6 divides this difference evenly.

30 \div 6 = 5

Step 3: Since 30 ÷ 6 gives a whole number with no remainder, 6 divides 30 exactly.

6 \mid 30

Step 4: Therefore, 23 and 53 are equivalent mod 6. You can verify: 23 = 3 × 6 + 5 and 53 = 8 × 6 + 5. Both leave remainder 5.

23 \equiv 53 \pmod{6}

Answer: Yes, 23 ≡ 53 (mod 6) because their difference 30 is divisible by 6.

Another Example

This example shows how to reduce a number to its smallest positive representative in a given modulus, rather than just checking whether two given numbers are equivalent.

Problem: Find the smallest positive integer b such that b ≡ 47 (mod 9).

Step 1: Divide 47 by 9 to find the remainder.

47 = 5 \times 9 + 2

Step 2: The remainder is 2. Any integer equivalent to 47 mod 9 must also leave remainder 2 when divided by 9.

47 \equiv 2 \pmod{9}

Step 3: The smallest positive integer with remainder 2 when divided by 9 is simply 2 itself.

b = 2

Step 4: Verify: 47 − 2 = 45, and 45 ÷ 9 = 5. Since 9 divides 45 exactly, the equivalence holds.

9 \mid 45 \quad \checkmark

Answer: The smallest positive integer equivalent to 47 mod 9 is b = 2.

Frequently Asked Questions

What is the difference between modular equivalence and equality?

Equality means two values are exactly the same number. Modular equivalence means two integers share the same remainder when divided by n, but the integers themselves can be very different. For example, 3 and 15 are not equal, but they are equivalent mod 4 because both leave remainder 3 when divided by 4.

How do you check if two numbers are congruent mod n?

Subtract the smaller number from the larger, then check whether n divides the result with no remainder. If it does, the two numbers are congruent (equivalent) mod n. Alternatively, you can divide each number by n separately and compare their remainders — if the remainders match, the numbers are congruent.

Can negative numbers be modularly equivalent?

Yes. Modular equivalence applies to all integers, including negatives. For example, −3 ≡ 7 (mod 5) because 7 − (−3) = 10, and 5 divides 10. You can also verify that both −3 and 7 have the same remainder of 2 when divided by 5 (using the convention that the remainder is non-negative).

Modular Equivalence (Congruence) vs. Equality

	Modular Equivalence (Congruence)	Equality
Definition	a and b leave the same remainder when divided by n	a and b are the exact same number
Notation	a ≡ b (mod n)	a = b
Depends on a modulus?	Yes — two numbers can be equivalent under one modulus but not another	No — equality is absolute
Number of solutions	Infinitely many integers are equivalent to any given integer mod n	Only one number equals a given number

Why It Matters

Modular equivalence is foundational in number theory, cryptography (including RSA encryption), and computer science (hash functions, checksums). You will encounter it in competition math when solving problems about divisibility, last digits, and cyclic patterns. It also underlies everyday applications like clock arithmetic — 15:00 and 3:00 are equivalent mod 12.

Common Mistakes

Mistake: Confusing the modulus with the remainder. For example, writing 17 ≡ 4 (mod 17) when you mean 17 ≡ 1 (mod 4).

Correction: The number after 'mod' is the modulus (the divisor), not the remainder. Always place the divisor in the (mod …) position. Here, dividing by 4 gives remainder 1, so 17 ≡ 1 (mod 4).

Mistake: Thinking that a ≡ b (mod n) means a equals b. Students sometimes treat the ≡ symbol as a regular equals sign and substitute freely in non-modular expressions.

Correction: The symbol ≡ indicates congruence, not equality. You can only use it within modular arithmetic operations. For instance, 2 ≡ 12 (mod 5) does not mean you can replace 2 with 12 in an ordinary algebraic equation.

Related Terms

Integers — The set of numbers modular equivalence applies to
Equivalence Relation — Modular equivalence is an equivalence relation
Remainder — Shared remainder defines modular equivalence
Modular Equivalence Rules — Rules for adding, multiplying, and powering mod n
Modulo n — The modular system in which equivalence is defined
Divisibility — n divides (a − b) is the core test for equivalence
Equivalence Class — Set of all integers equivalent to a given value mod n