👁 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

Residues

Study Practice Revise 🔒 Test

Introduction to Residues

When we divide one number by another, the answer usually consists of two parts: the quotient and the remainder. The remainder is what is left over after dividing as many times as possible without going negative. This leftover part is called the residue in mathematics.

Understanding residues is crucial because they help simplify calculations, especially when dealing with large numbers. They form the foundation of modular arithmetic, a powerful tool used in number theory and many competitive exam problems. Residues allow us to work with numbers in cycles or patterns, making complex problems easier to solve.

Division Algorithm and Residues

The Division Algorithm is a fundamental concept that formalizes how division works with integers. It states that for any integer a and any positive integer b, there exist unique integers q (quotient) and r (remainder) such that:

\[ a = bq + r, \quad 0 \leq r < b \]

where:

  • a = dividend (the number to be divided)
  • b = divisor (the number by which we divide, with \(b > 0\))
  • q = quotient (how many times b fits into a)
  • r = remainder or residue (what is left after division)

This means when you divide a by b, you get a quotient q and a remainder r that is always less than b. The remainder is what we call the residue of a modulo b.

graph TD    A[Start with integers a and b (b > 0)] --> B[Divide a by b]    B --> C[Find quotient q = floor(a/b)]    C --> D[Calculate remainder r = a - bq]    D --> E{Is 0 ≤ r < b?}    E -- Yes --> F[Residue r found]    E -- No --> B

Modular Arithmetic and Congruences

Modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" upon reaching a certain value called the modulus. It is like the arithmetic of a clock, where after 12 hours, the count resets to 1.

We write:

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

which means: a is congruent to b modulo m.

This is true if and only if m divides the difference \(a - b\), i.e.,

\[ m \mid (a - b) \]

In simpler terms, two numbers are congruent modulo m if they leave the same residue when divided by m.

Examples of Residue Classes modulo 5
Integer Residue modulo 5 Congruence Class
72\(7 \equiv 2 \pmod{5}\)
122\(12 \equiv 2 \pmod{5}\)
-32\(-3 \equiv 2 \pmod{5}\)
00\(0 \equiv 0 \pmod{5}\)
150\(15 \equiv 0 \pmod{5}\)

Notice how numbers like 7, 12, and -3 all belong to the same residue class modulo 5 because they leave the same remainder 2 when divided by 5.

Properties of Residues

Residues under modular arithmetic follow several important properties that mirror normal arithmetic but with the modulus applied:

  • Closure: Addition, subtraction, and multiplication of residues modulo m always result in another residue modulo m.
  • Associative Property: \((a + b) + c \equiv a + (b + c) \pmod{m}\), and similarly for multiplication.
  • Commutative Property: \(a + b \equiv b + a \pmod{m}\), and \(a \times b \equiv b \times a \pmod{m}\).
  • Distributive Property: \(a \times (b + c) \equiv a \times b + a \times c \pmod{m}\).

These properties allow us to simplify complex expressions by reducing intermediate results modulo m, making calculations manageable and efficient.

Formula Bank

Division Algorithm
\[ a = bq + r, \quad 0 \leq r < b \]
where: \(a\) = dividend, \(b\) = divisor (\(b > 0\)), \(q\) = quotient, \(r\) = remainder
Congruence Definition
\[ a \equiv b \pmod{m} \iff m \mid (a - b) \]
where: \(a, b\) = integers; \(m\) = modulus (\(m > 0\))
Addition in Modular Arithmetic
\[ (a + b) \bmod m = [(a \bmod m) + (b \bmod m)] \bmod m \]
where: \(a, b\) = integers; \(m\) = modulus
Multiplication in Modular Arithmetic
\[ (a \times b) \bmod m = [(a \bmod m) \times (b \bmod m)] \bmod m \]
where: \(a, b\) = integers; \(m\) = modulus
Power Modulo (Exponentiation)
\[ a^n \bmod m = \left[(a \bmod m)^n\right] \bmod m \]
where: \(a\) = base, \(n\) = exponent, \(m\) = modulus

Worked Examples

Example 1: Finding the Residue of a Number Easy
Find the remainder when 12345 is divided by 7.

Step 1: Use the division algorithm: \(12345 = 7q + r\), where \(0 \leq r < 7\).

Step 2: Divide 12345 by 7:

\(7 \times 1763 = 12341\)

Step 3: Calculate remainder:

\(r = 12345 - 12341 = 4\)

Answer: The residue (remainder) is 4. So, \(12345 \equiv 4 \pmod{7}\).

Example 2: Solving a Congruence Equation Medium
Solve for \(x\) in the congruence \(4x \equiv 3 \pmod{7}\).

Step 1: We want to find \(x\) such that \(4x \equiv 3 \pmod{7}\).

Step 2: Find the modular inverse of 4 modulo 7. The modular inverse \(4^{-1}\) satisfies:

\(4 \times 4^{-1} \equiv 1 \pmod{7}\).

Step 3: Test integers 1 to 6:

  • \(4 \times 2 = 8 \equiv 1 \pmod{7}\) since \(8 - 7 = 1\).

So, \(4^{-1} \equiv 2 \pmod{7}\).

Step 4: Multiply both sides of original congruence by 2:

\(2 \times 4x \equiv 2 \times 3 \pmod{7}\)

\( (2 \times 4) x \equiv 6 \pmod{7}\)

\(8x \equiv 6 \pmod{7}\)

Since \(8 \equiv 1 \pmod{7}\), this simplifies to:

\(x \equiv 6 \pmod{7}\)

Answer: \(x \equiv 6 \pmod{7}\). The solution is all integers congruent to 6 modulo 7.

Example 3: Using Residues to Simplify Large Powers Hard
Find the residue of \(3^{100}\) modulo 5.

Step 1: Calculate powers of 3 modulo 5 to find a pattern:

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

Step 2: Notice the pattern repeats every 4 powers (since \(3^4 \equiv 1\)).

Step 3: Find remainder when 100 is divided by 4:

\(100 \div 4 = 25\) with remainder 0.

Step 4: Use the pattern:

\(3^{100} \equiv (3^4)^{25} \equiv 1^{25} \equiv 1 \pmod{5}\)

Answer: The residue of \(3^{100}\) modulo 5 is 1.

Example 4: Application in Divisibility Hard
Check if \(2^{50} + 3^{50}\) is divisible by 7 using residues.

Step 1: Find \(2^{50} \pmod{7}\) and \(3^{50} \pmod{7}\).

Step 2: Calculate the pattern length (order) for 2 modulo 7:

  • \(2^1 = 2 \pmod{7}\)
  • \(2^2 = 4 \pmod{7}\)
  • \(2^3 = 8 \equiv 1 \pmod{7}\)

So, \(2^3 \equiv 1 \pmod{7}\), cycle length is 3.

Step 3: Find \(50 \bmod 3\):

\(50 \div 3 = 16\) remainder 2.

Therefore, \(2^{50} \equiv 2^{2} = 4 \pmod{7}\).

Step 4: Calculate the pattern length for 3 modulo 7:

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

Cycle length is 6.

Step 5: Find \(50 \bmod 6\):

\(50 \div 6 = 8\) remainder 2.

Therefore, \(3^{50} \equiv 3^{2} = 2 \pmod{7}\).

Step 6: Sum residues modulo 7:

\(2^{50} + 3^{50} \equiv 4 + 2 = 6 \pmod{7}\).

Step 7: Since the sum modulo 7 is 6 (not 0), the number is not divisible by 7.

Answer: \(2^{50} + 3^{50}\) is not divisible by 7.

Example 5: Residues in Real-Life Context Medium
Find the remainder when INR 1,23,456 is divided by 99.

Step 1: Use the division algorithm: \(123456 = 99q + r\), find \(r\).

Step 2: Divide 123456 by 99:

Calculate approximate quotient:

\(99 \times 1247 = 99 \times 1200 + 99 \times 47 = 118800 + 4653 = 123453\)

Step 3: Calculate remainder:

\(r = 123456 - 123453 = 3\)

Answer: The remainder when INR 1,23,456 is divided by 99 is 3.

Tips & Tricks

Tip: Always reduce numbers modulo \(m\) at each step to simplify calculations.

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

Tip: Use the modular inverse to solve linear congruences efficiently.

When to use: When solving equations of the form \(ax \equiv b \pmod{m}\).

Tip: Recognize patterns in powers modulo \(m\) to avoid lengthy calculations.

When to use: When calculating large exponents modulo \(m\).

Tip: Apply the division algorithm to quickly find remainders without performing full division.

When to use: When asked to find the remainder of large numbers divided by smaller ones.

Tip: Use congruence properties to break down complex expressions into simpler parts.

When to use: When simplifying sums, products, or powers under modulo.

Common Mistakes to Avoid

❌ Confusing remainder with quotient in division problems.
✓ Remember the remainder \(r\) satisfies \(0 \leq r < b\), not the quotient.
Why: Students often misinterpret division results under pressure.
❌ Ignoring the modulus when performing arithmetic operations.
✓ Always reduce intermediate results modulo \(m\) to keep numbers manageable.
Why: Skipping modulo reduction leads to unnecessarily large numbers and errors.
❌ Assuming modular division works like normal division.
✓ Division modulo \(m\) requires the modular inverse; it is not straightforward division.
Why: Modular division is only defined when the divisor and modulus are coprime.
❌ Misapplying properties of congruences, such as assuming \(a \equiv b \pmod{m}\) implies \(a = b\).
✓ Understand that congruence means equality modulo \(m\), not absolute equality.
Why: Misunderstanding equivalence classes leads to incorrect conclusions.
❌ Forgetting to check if the modular inverse exists before solving congruences.
✓ Verify \(\gcd(a, m) = 1\) before finding the modular inverse of \(a\) modulo \(m\).
Why: Without this condition, the inverse does not exist and the equation has no unique solution.

Division Algorithm

\[a = bq + r, \quad 0 \leq r < b\]

Expresses any integer a as a multiple of b plus a remainder r.

a = Dividend
b = Divisor (b > 0)
q = Quotient
r = Remainder

Congruence Definition

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

Two numbers a and b are congruent modulo m if their difference is divisible by m.

a, b = Integers
m = Modulus (m > 0)

Addition in Modular Arithmetic

\[(a + b) \bmod m = [(a \bmod m) + (b \bmod m)] \bmod m\]

Sum of residues modulo m.

a, b = Integers
m = Modulus

Multiplication in Modular Arithmetic

\[(a \times b) \bmod m = [(a \bmod m) \times (b \bmod m)] \bmod m\]

Product of residues modulo m.

a, b = Integers
m = Modulus

Power Modulo (Exponentiation)

\[a^n \bmod m = \left[(a \bmod m)^n\right] \bmod m\]

Calculating large powers modulo m using residues.

a = Base
n = Exponent
m = Modulus
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
Residues · 10 free messages
Ask me anything about this subtopic. You have 10 free messages this session — chat history isn't saved in preview.