👁 Preview — Study, Practice and Revise are open; mock tests and the rest of the syllabus unlock on subscription. Unlock all · ₹4,999
← Back to Number System
Study mode

Congruence

Study Practice Revise 🔒 Test

Introduction to Congruence

In everyday life, when we divide a number by another, we often focus on the remainder left after division. For example, if you have Rs.38 and you pay Rs.10 notes, you will have Rs.8 left after giving out three Rs.10 notes. This idea of focusing on the remainder is the foundation of congruence in mathematics.

Congruence is a way to say that two numbers have the same remainder when divided by a certain number, called the modulus. This concept is very useful in number theory and appears frequently in competitive exams.

We write this relationship as:

\[ a \equiv b \pmod{m} \]

This reads as: "a is congruent to b modulo m."

Here, \(a\) and \(b\) are integers, and \(m\) is a positive integer called the modulus. This means that when \(a\) and \(b\) are divided by \(m\), they leave the same remainder.

Definition of Congruence

Two integers \(a\) and \(b\) are said to be congruent modulo \(m\) if their difference \((a - b)\) is exactly divisible by \(m\). In other words, \(m\) divides \((a - b)\).

\[ a \equiv b \pmod{m} \iff m \mid (a - b) \]

Here, the symbol \(\mid\) means "divides". So, \(m \mid (a - b)\) means \(a - b\) is a multiple of \(m\).

For example, consider \(a = 38\), \(b = 8\), and \(m = 10\). Then, \(38 - 8 = 30\), and since 30 is divisible by 10, we say:

\[ 38 \equiv 8 \pmod{10} \]

Properties of Congruence

Congruence has three important properties that make it an equivalence relation:

  • Reflexive: Every number is congruent to itself modulo \(m\). That is, \(a \equiv a \pmod{m}\).
  • Symmetric: If \(a \equiv b \pmod{m}\), then \(b \equiv a \pmod{m}\).
  • Transitive: If \(a \equiv b \pmod{m}\) and \(b \equiv c \pmod{m}\), then \(a \equiv c \pmod{m}\).
Number line: a b (a - b) divisible by m

Modulo Operation and Residues

The modulo operation finds the remainder when one number is divided by another. For example, \(38 \mod 10 = 8\) because when 38 is divided by 10, the remainder is 8.

Every integer belongs to a residue class modulo \(m\), which is the set of all integers that leave the same remainder when divided by \(m\).

For modulus \(m = 5\), the possible remainders (or residues) are 0, 1, 2, 3, and 4. These form the residue classes:

Integer \(a\) Residue \(a \mod 5\) Residue Class
7 2 \(\{..., -8, -3, 2, 7, 12, 17, ...\}\)
13 3 \(\{..., -7, -2, 3, 8, 13, 18, ...\}\)
20 0 \(\{..., -10, -5, 0, 5, 10, 15, 20, ...\}\)

Notice that all integers in the same residue class are congruent modulo 5.

Arithmetic Operations under Modulo

Congruence is preserved under addition, subtraction, and multiplication. This means:

\[ \begin{cases} a \equiv b \pmod{m}, \quad c \equiv d \pmod{m} \\ \Rightarrow a + c \equiv b + d \pmod{m} \\ a - c \equiv b - d \pmod{m} \\ a \cdot c \equiv b \cdot d \pmod{m} \end{cases} \]

This property allows us to simplify calculations by reducing numbers modulo \(m\) at every step.

Worked Examples

Example 1: Checking Congruence Easy
Check if \(38 \equiv 8 \pmod{10}\).

Step 1: Calculate the difference \(38 - 8 = 30\).

Step 2: Check if 30 is divisible by 10.

Since \(30 \div 10 = 3\) with no remainder, 30 is divisible by 10.

Answer: Therefore, \(38 \equiv 8 \pmod{10}\) is true.

Example 2: Solving Linear Congruence Medium
Find \(x\) such that \(7x \equiv 1 \pmod{11}\).

Step 1: We want to find \(x\) such that when multiplied by 7 and divided by 11, the remainder is 1.

Step 2: This means \(x\) is the modular inverse of 7 modulo 11.

Step 3: Find \(x\) such that \(7x \equiv 1 \pmod{11}\). Try values of \(x\) from 1 to 10:

  • \(7 \times 1 = 7 \equiv 7 \pmod{11}\)
  • \(7 \times 2 = 14 \equiv 3 \pmod{11}\)
  • \(7 \times 3 = 21 \equiv 10 \pmod{11}\)
  • \(7 \times 4 = 28 \equiv 6 \pmod{11}\)
  • \(7 \times 5 = 35 \equiv 2 \pmod{11}\)
  • \(7 \times 6 = 42 \equiv 9 \pmod{11}\)
  • \(7 \times 7 = 49 \equiv 5 \pmod{11}\)
  • \(7 \times 8 = 56 \equiv 1 \pmod{11}\)

Step 4: Since \(7 \times 8 \equiv 1 \pmod{11}\), the modular inverse of 7 modulo 11 is 8.

Answer: \(x = 8\).

Example 3: Application in Remainder Problems Hard
Find the remainder when \(3^{100}\) is divided by 7.

Step 1: Directly calculating \(3^{100}\) is impossible by hand, so use modular arithmetic properties.

Step 2: Find the pattern of powers of 3 modulo 7:

  • \(3^1 \equiv 3 \pmod{7}\)
  • \(3^2 = 9 \equiv 2 \pmod{7}\)
  • \(3^3 = 3^2 \times 3 = 2 \times 3 = 6 \equiv 6 \pmod{7}\)
  • \(3^4 = 3^3 \times 3 = 6 \times 3 = 18 \equiv 4 \pmod{7}\)
  • \(3^5 = 3^4 \times 3 = 4 \times 3 = 12 \equiv 5 \pmod{7}\)
  • \(3^6 = 3^5 \times 3 = 5 \times 3 = 15 \equiv 1 \pmod{7}\)

Step 3: Notice that \(3^6 \equiv 1 \pmod{7}\). This means powers of 3 repeat every 6 steps modulo 7.

Step 4: Express 100 as \(100 = 6 \times 16 + 4\).

Step 5: Using this,

\[ 3^{100} = 3^{6 \times 16 + 4} = (3^6)^{16} \times 3^4 \equiv 1^{16} \times 3^4 \equiv 3^4 \pmod{7} \]

From Step 2, \(3^4 \equiv 4 \pmod{7}\).

Answer: The remainder when \(3^{100}\) is divided by 7 is 4.

Example 4: Using Properties to Simplify Medium
Simplify \((15 + 28) \mod 6\) using congruence properties.

Step 1: Find residues of 15 and 28 modulo 6:

  • \(15 \mod 6 = 3\) (since \(15 = 6 \times 2 + 3\))
  • \(28 \mod 6 = 4\) (since \(28 = 6 \times 4 + 4\))

Step 2: Use the property \(a + b \equiv (a \mod m) + (b \mod m) \pmod{m}\):

\[ (15 + 28) \mod 6 \equiv (3 + 4) \mod 6 = 7 \mod 6 = 1 \]

Answer: \((15 + 28) \mod 6 = 1\).

Example 5: Application in Number Theory (Chinese Remainder Theorem) Hard
Find an integer \(x\) such that:
\[ x \equiv 2 \pmod{3}, \quad x \equiv 3 \pmod{5}, \quad x \equiv 2 \pmod{7} \]

Step 1: The moduli 3, 5, and 7 are pairwise coprime.

Step 2: The product of moduli is \(M = 3 \times 5 \times 7 = 105\).

Step 3: Calculate \(M_i = \frac{M}{m_i}\) for each modulus:

  • \(M_1 = 105 / 3 = 35\)
  • \(M_2 = 105 / 5 = 21\)
  • \(M_3 = 105 / 7 = 15\)

Step 4: Find modular inverses \(y_i\) such that \(M_i y_i \equiv 1 \pmod{m_i}\):

  • Find \(y_1\) such that \(35 y_1 \equiv 1 \pmod{3}\). Since \(35 \equiv 2 \pmod{3}\), solve \(2 y_1 \equiv 1 \pmod{3}\). Trying \(y_1=2\), \(2 \times 2 = 4 \equiv 1 \pmod{3}\). So, \(y_1=2\).
  • Find \(y_2\) such that \(21 y_2 \equiv 1 \pmod{5}\). Since \(21 \equiv 1 \pmod{5}\), \(1 \times y_2 \equiv 1 \pmod{5}\), so \(y_2=1\).
  • Find \(y_3\) such that \(15 y_3 \equiv 1 \pmod{7}\). Since \(15 \equiv 1 \pmod{7}\), \(1 \times y_3 \equiv 1 \pmod{7}\), so \(y_3=1\).

Step 5: Calculate \(x\) using the formula:

\[ x \equiv \sum_{i=1}^3 a_i M_i y_i \pmod{M} \]

Where \(a_1=2, a_2=3, a_3=2\).

\[ x \equiv 2 \times 35 \times 2 + 3 \times 21 \times 1 + 2 \times 15 \times 1 = 140 + 63 + 30 = 233 \]

Step 6: Find \(x \mod 105\):

\[ 233 \mod 105 = 233 - 2 \times 105 = 233 - 210 = 23 \]

Answer: \(x \equiv 23 \pmod{105}\). So, \(x = 23\) is a solution.

Definition of Congruence

\[a \equiv b \pmod{m} \iff m \mid (a - b)\]

Two integers a and b are congruent modulo m if m divides their difference

a, b = integers
m = positive integer modulus

Properties of Congruence

\[\begin{cases} a \equiv a \pmod{m} \\ a \equiv b \pmod{m} \implies b \equiv a \pmod{m} \\ a \equiv b \pmod{m} \text{ and } b \equiv c \pmod{m} \implies a \equiv c \pmod{m} \end{cases}\]

Reflexive, symmetric, and transitive properties

a, b, c = integers
m = modulus

Arithmetic under Modulo

\[\begin{cases} a \equiv b \pmod{m} \, , \, c \equiv d \pmod{m} \\ \Rightarrow a + c \equiv b + d \pmod{m} \\ a - c \equiv b - d \pmod{m} \\ a \cdot c \equiv b \cdot d \pmod{m} \end{cases}\]

Addition, subtraction, and multiplication preserve congruence

a, b, c, d = integers
m = modulus

Modular Inverse

\[a \cdot a^{-1} \equiv 1 \pmod{m}\]

Inverse of a modulo m exists if gcd(a, m) = 1

a = integer
\(a^{-1}\) = modular inverse of a
m = modulus

Tips & Tricks

Tip: Always reduce numbers modulo \(m\) before performing operations to simplify calculations.

When to use: When dealing with large numbers or complex expressions in modular arithmetic.

Tip: Use properties of congruence (addition, subtraction, multiplication) to break down complex problems.

When to use: When solving modular equations or simplifying expressions.

Tip: Check \(\gcd(a, m) = 1\) before finding modular inverse; if not 1, inverse does not exist.

When to use: When solving linear congruences involving modular inverses.

Tip: For exponentiation modulo \(m\), use cyclicity or Euler's theorem to reduce powers.

When to use: When calculating remainders of large powers.

Tip: Write out residue classes for small moduli to visualize equivalence classes.

When to use: When first learning modular arithmetic or verifying congruences.

Common Mistakes to Avoid

❌ Confusing equality with congruence (thinking \(a \equiv b \pmod{m}\) means \(a = b\)).
✓ Understand that congruence means \(a\) and \(b\) differ by a multiple of \(m\), not necessarily equal.
Why: Students often interpret congruence as strict equality rather than equivalence modulo \(m\).
❌ Forgetting to reduce intermediate results modulo \(m\), leading to large unnecessary calculations.
✓ Reduce each step modulo \(m\) to keep numbers manageable and simplify calculations.
Why: Lack of practice in modular arithmetic leads to inefficient problem solving.
❌ Assuming modular inverse exists for any number \(a\) modulo \(m\).
✓ Check \(\gcd(a, m) = 1\) before attempting to find inverse.
Why: Inverse exists only if \(a\) and \(m\) are coprime.
❌ Misapplying properties of congruence, such as dividing both sides by a number without checking conditions.
✓ Division in modular arithmetic is valid only when divisor has an inverse modulo \(m\).
Why: Division is not straightforward in modular arithmetic and requires care.
❌ Mixing up modulus in multi-step problems, applying wrong modulus in calculations.
✓ Keep track of modulus throughout the problem and verify at each step.
Why: Multiple moduli in problems can confuse students if not carefully managed.
Curated videos per subtopic
Top YouTube explainers, AI-ranked for your exam and language. Unlocks with subscription.
Unlock

Try Practice next.

Progress tracking is paywalled — subscribe to mark subtopics as understood and save your streak.

Go to practice →
Ask a doubt
Congruence · 10 free messages
Ask me anything about this subtopic. You have 10 free messages this session — chat history isn't saved in preview.