Two integers are modular equivalent (equivalent mod n) if they gives the same remainder when it is divided by n. Modular equivalence is how modulo math says that two numbers are the same for its purposes. On the circle of the Modulo Math page, two such numbers land on the same sector. I'll start with examples, then give the formal definition. After that we'll check each property on real numbers and see why the idea saves work in a calculation.

• What does modular equivalence mean ?
• Formal Definition
• Properties of Modulo Equivalence.
• Why is modular equivalence useful ?

What does modular equivalence mean ?

The remainder alone decides where a number lands on the circle of modulo n. So two different integers can behave in exactly the same way, as long as their remainders match. The examples below compare three numbers with 2 in modulo 5.

Example 01

Each line of the example divides both numbers by 5 and compares the remainders. The remainders are all 2, so every pair is equivalent. The same comparison works for any n, and the next section turns it into a formula.

Two integer 2 and 7 are (equivalent mod 5) because (2 mod 5) = (7 mod 5)

Two integer 2 and 12 are (equivalent mod 5) because (2 mod 5) = (12 mod 5)

Two integer 2 and 17 are (equivalent mod 5) because (2 mod 5) = (17 mod 5)

Look at the differences in the example. 7 - 2 = 5, 12 - 2 = 10 and 17 - 2 = 15 are all multiples of 5. This is not a coincidence, and the formal definition in the next section uses exactly this test. The numbers 2, 7, 12, 17 and so on, together with -3, -8 and so on, form one group. Every member of the group is equivalent mod 5 to every other member, and the group is called the equivalence class of 2 mod 5.

• Modulo 5 has five classes : every integer falls into exactly one of the classes of 0, 1, 2, 3 and 4.
• Equivalent is not the same as equal : 2 and 17 are different integers. They are equal only after reduction mod 5.
• Negative numbers belong to a class too : -3 mod 5 = 2, so -3 is in the class of 2.

Formal Definition

The definition by remainders needs a division before you can compare. The formal definition avoids that step. It uses a single subtraction and a divisibility test, which is easier to use in a proof.

If you are scared of mathematical symbol, forget about this and just stick to the definition explained above. You can come back later when you become more familiar/comfortable to mathematical symbols.

Anyway, the formal expression of the definition of Modular Equivalence is as follows :

Figure 1 states the definition as one line, and then gives the short notation that the property list uses.

Figure 1. The formal definition. a and b are equivalent mod n exactly when n divides a - b.

• n | (a - b) means n divides a - b : a - b is an integer multiple of n. For a = 17, b = 2 and n = 5, a - b = 15 = 3 x 5.
• The symbol ≡ is not = : it reads as is equivalent to. The notation a ≡_n b below the double bar is a shorter form of a ≡ b mod n.
• If and only if works both ways : equivalent numbers always have a difference divisible by n. And any two numbers with such a difference are always equivalent.

The two definitions agree. Write a = q₁n + r and b = q₂n + r with the same remainder r. Then a - b = (q₁ - q₂)n, which is a multiple of n. The subtraction test also works directly for negative numbers. For example, -3 - 2 = -5, so -3 ≡₅ 2 without any question about the sign of a remainder.

Properties of Modulo Equivalence.

The properties say which operations keep two equivalent numbers equivalent. Three of them always work. The fourth, cancellation, needs a condition, and that condition is the one to remember.

Modulo Equivalence has following properties. Don't try to memorize this. Just try to understand what does it mean by each of the properties for now. When you see some real application that would use some of these properties and you can come back here and you will underand the practical importance of these properties.

Figure 2 lists the four properties. The first three apply one operation with c to both sides. The last one removes a common factor c from both sides.

Figure 2. Properties of modular equivalence. Addition, subtraction and multiplication always keep equivalence. Division by c keeps it only when c and n are relatively prime.

Let's check each line with n = 5, a = 2, b = 7 and c = 3. We already know 2 ≡₅ 7.

• Addition : 2 + 3 = 5 and 7 + 3 = 10. Both are 0 mod 5, so 5 ≡₅ 10.
• Subtraction : 2 - 3 = -1 and 7 - 3 = 4. -1 mod 5 is 4, so -1 ≡₅ 4.
• Multiplication : 2 x 3 = 6 and 7 x 3 = 21. Both are 1 mod 5, so 6 ≡₅ 21.
• Cancellation needs relatively prime c and n : 3 and 5 have no common factor, so 6 ≡₅ 21 gives back 2 ≡₅ 7. Now try n = 6 and c = 2. 2 x 1 = 2 and 2 x 4 = 8 are equivalent mod 6, because 8 - 2 = 6. But 1 and 4 are not equivalent mod 6. The common factor 2 of c and n breaks the cancellation.

Why is modular equivalence useful ?

The properties let you replace a number by any member of its class before you calculate. So you can reduce large numbers first and keep every intermediate result small. This section shows three uses of that idea.

The first use is a smaller calculation. To find (123 x 456) mod 7, reduce each factor first. 123 mod 7 = 4 and 456 mod 7 = 1, so the result is (4 x 1) mod 7 = 4. The full product 56088 gives the same 4, but you never need to compute it. The same idea works for powers. 3⁴ = 81 ≡₅ 1, so 3¹⁰⁰ = (3⁴)²⁵ ≡₅ 1²⁵ = 1.

The second use is a quick check. A number is equivalent mod 9 to the sum of its decimal digits, because 10 ≡₉ 1. For 123 x 456, the digit sums are 6 and 15, and 6 x 15 = 90 ≡₉ 0. The product 56088 has digit sum 27, which is also 0 mod 9, so the product passes the check. The third use is in bit processing. Any sum of bits in modulo 2 depends only on how many of the bits are 1. So a parity bit or a CRC can be computed piece by piece, reducing mod 2 at every step.

• Reduce early : in a sum or a product mod n, you can reduce every term first. The result is the same, and the numbers stay smaller than n.
• Division is the exception : you cannot cancel a factor that shares a divisor with n, as the n = 6 example shows.
• A check can miss an error : the mod 9 check only detects errors that change the class mod 9. Swapping two digits, for example, is not detected.