Properties of Congruence in Discrete Mathematics

---

---

The congruence logic is a way to express that two numbers are "basically the same" in the context of a given modulus. The concept of congruence is quite useful of modular arithmetic. It is used for simplifying calculations and patterns across integers. This topic is useful in cryptography and coding theory.

In this chapter, we will see some important properties of congruence and go through some examples to show how congruence behaves like equality in modular arithmetic.

What is Congruence?

When we say two numbers a and b are congruent modulo n (written as a ≡ b (mod n)), it means that a and b leave the same remainder when it is divided by n. This concept is similar to equality but within a circular system where numbers "wrap around" after reaching the the modulus n.

For example, if we say 15 ≡ 3 (mod 12), it is like we are saying that when we divide both 15 and 3 by 12, they each will have a remainder of 3.

Congruence as an Equivalence Relation

Congruence relations work just like equality. This is because they follow three basic properties: reflexivity, symmetry, and transitivity. These three properties make congruence an equivalence relation. And it behaves consistently when applied to different numbers in a given modulus. Let us see these properties one by one.

Reflexivity

Any integer a is always congruent to itself. In other words, a ≡ a (mod n) for any integer a and modulus n. This may seem obvious. But it is important because it sets up congruence as a reliable system. For instance if we take number 7. It means 7 ≡ 7 (mod 3). Since both instances of 7 have the same remainder when divided by 3 (a remainder of 1).

Symmetry

If a ≡ b (mod n), then b ≡ a (mod n) as well. If two numbers are congruent in one direction, they are congruent in the other direction also. This is making the relationship reciprocal. For example, if 18 ≡ 6 (mod 12), then 6 ≡ 18 (mod 12) as well. Both numbers leave a remainder of 6 when divided by 12. In this case, congruence holds in either direction.

Transitivity

If a ≡ b (mod n) and b ≡ c (mod n), then a ≡ c (mod n) as well. This property gives us the provision to "pass along" congruence between multiple numbers. For example, consider 14 ≡ 2 (mod 6) and 2 ≡ 8 (mod 6). By transitivity, 14 ≡ 8 (mod 6). Since each pair has the same remainder when divided by 6.

Together, reflexivity, symmetry, and transitivity says that congruence behaves consistently like regular equality.

Arithmetic Properties of Congruence

The congruence property follows specific arithmetic properties which is like add, subtract, and multiply congruent numbers without disrupting the system. These properties make congruence extremely practical, when we are doing calculations in large numbers.

Addition and Subtraction

If two pairs of numbers are congruent, then we can add them and subtract them. These operations will return results that are also congruent.

So, if a ≡ b (mod n) and c ≡ d (mod n), then −

• a + c ≡ b + d (mod n)
• a – c ≡ b − d (mod n)

This property is useful because it gives us the provision to combine or separate congruent numbers without changing their congruence status.

Example

Let us say 15 3(mod6) and 10 4(mod6).

For addition: 15 + 10 ≡ 3 + 4 (mod 6). This simplifies to 25 ≡ 7 (mod 6). Since 7 and 25 both leave a remainder of 1 when divided by 6, they are congruent.

For subtraction: 15 – 10 ≡ 3 − 4 (mod 6). By simplifying them, we get 5 ≡ −1 (mod 6). Negative remainders are often adjusted by adding the modulus, so −1 (mod 6) is the same as 5.

Multiplication

If we see the multiplication operation it also preserves congruence.

If a ≡ b (mod n) and c ≡ d (mod n), then

$$\mathrm{a \:\times\: c \:\equiv\: b \:\times\: d \: (\text{mod} \: n)}$$

This property simplifies the multiplication across congruent pairs.

Example

If 4 1(mod3) and 5 2(mod3). Then, multiplying gives −

$$\mathrm{4 \:\times\: 5 \:\equiv \:1 \:\times\: 2 \: (\text{mod} \: 3)}$$

It simplifies to 20 ≡ 2 (mod 3)

Multiplying congruent numbers can help reduce large calculations into smaller, more manageable ones.

Substitution in Congruence

Another most useful aspects of congruence is the ability to substitute numbers with any congruent equivalent. In other words, if a b(modn), then we can replace a with b in any congruence without affecting the result. This idea helps streamline complex calculations by reducing the numbers to simpler representatives within the same remainder class.

Example

To find the remainder of 3491 divided by 9, we can break it down using congruences −

Break 3491 into 3000 + 400 + 90 + 1.

Since 3000 ≡ 0 (mod 9), 400 ≡ 4 (mod 9), 90 ≡ 0 (mod 9) and 1 ≡ 1 (mod 9), we can replace each part with its congruent equivalent.

By adding these results gives 0 + 4 + 0 + 1 = 5. So, 3491 ≡ 5 (mod 9) and the remainder when 3491 is divided by 9 is 5. This substitution trick is so much helpful for large calculations. It is used to make calculation manageable by simplifying each component.

Limitations of Congruence and Division

Congruence allows addition, subtraction, and multiplication. But division requires more caution. Generally, the division is not directly applicable in congruences unless specific conditions are met.

If a × d ≡ b × d (mod n), we cannot simply cancel d from both sides unless d and n share no common factors other than 1.

Example

Suppose 18 ≡ 42 (mod 8), and we want to divide by 6. If we want to cancel the 6, we get an invalid result. This is because both 6 and 8 share the factor 2. However, if there is no shared factor, such as in 21 ≡ 7 (mod 5), we can safely divide by 3.

So in other words, division within congruences only works when the divisor and modulus are "co-prime" (They have no common factors other than 1).

Conclusion

In this chapter, we explained the properties of congruence in discrete mathematics. We began with the basics of congruence as an equivalence relation, exploring its reflexivity, symmetry, and transitivity, similar to normal equality. Then, we examined the arithmetic properties of congruence, including addition, subtraction, and multiplication, demonstrating how these operations preserve congruence.

We also discussed how substitution simplifies complex calculations, especially for large numbers. Finally, we highlighted the limitations of division in congruence.