0
0

Remainder Theorems (Euler/Fermat)

Introduction

जब exponents बहुत बड़े होते हैं, तो direct division से remainder निकालना मुश्किल होता है। ऐसे में Euler’s और Fermat’s Theorems बहुत powerful tools हैं। ये modular arithmetic को आसान बनाते हैं क्योंकि बड़े exponents को number properties के आधार पर छोटा किया जा सकता है।

Pattern: Remainder Theorems (Euler/Fermat)

Pattern

Euler और Fermat theorems बड़े powers के remainders को simplify करने के लिए modular reduction और special exponent rules का उपयोग करते हैं।

  • Fermat’s Little Theorem (FLT):
    अगर p एक prime है और a divisible नहीं है p से, तब:
    ap-1 ≡ 1 (mod p)
    ⇒ ak mod p = a(k mod (p-1)) mod p
  • Euler’s Theorem:
    अगर a और n coprime हों (GCD(a, n) = 1), तब:
    aφ(n) ≡ 1 (mod n)
    जहाँ φ(n) = उन numbers की count जो n से छोटे हैं और n के साथ coprime हैं।
    ⇒ ak mod n = a(k mod φ(n)) mod n
  • Euler’s Totient Function φ(n):
    φ(n) = n × (1 - 1/p₁) × (1 - 1/p₂) × … जहाँ p₁, p₂ distinct prime factors हैं।
    Example: φ(10) = 10 × (1-1/2) × (1-1/5) = 4
  • Shortcut Relation:
    - Modulus prime हो → Fermat use करें।
    - Modulus composite हो और base उससे coprime हो → Euler use करें।
    - Coprime न हो → modulus को split करें और Chinese Remainder Theorem या basic reduction use करें।

Step-by-Step Example

Question

7100 को 13 से divide करने पर remainder क्या होगा?

Solution

  1. Step 1: Modulus prime है

    13 prime है → Fermat’s Little Theorem use कर सकते हैं।

  2. Step 2: Fermat apply करें

    712 ≡ 1 (mod 13)

  3. Step 3: Exponent को (p-1) से mod करें

    100 mod 12 = 4 ⇒ 7100 ≡ 74 (mod 13)

  4. Step 4: 7⁴ mod 13 निकालें

    7² = 49 → 49 mod 13 = 10
    7⁴ = 10² = 100 → 100 mod 13 = 9

  5. Final Answer:

    Remainder = 9

  6. Quick Check:

    7¹² ≡ 1, इसलिए 7¹⁰⁰ = (7¹²)⁸ × 7⁴ → remainder 9. ✅

Quick Variations

1. Modulus prime होने पर → Fermat use करें।

2. Composite लेकिन base से coprime → Euler use करें।

3. Modulus और base में common factor हो → modulus को parts में split करके Chinese Remainder Theorem use करें।

4. बहुत बड़े exponents के लिए → exponent को बार-बार φ(n) से reduce करते जाएँ।

Trick to Always Use

  • Step 1: Modulus prime है क्या? → Yes → Fermat use करें।
  • Step 2: Prime नहीं लेकिन coprime → Euler use करें।
  • Step 3: Exponent को (p-1) या φ(n) से mod करके छोटा करें।
  • Step 4: Powers multiply करते समय numbers को mod n से reduce करते जाएँ।

Summary

Summary

  • Fermat: ap-1 ≡ 1 (mod p) जब p prime हो।
  • Euler: aφ(n) ≡ 1 (mod n) जब a और n coprime हों।
  • Exponent को (p-1) या φ(n) से reduce करके calculation आसान करें।
  • Large powers को modular squaring से compute करें ताकि numbers बड़े न हों।

Practice

(1/5)
1. Find the remainder when 2^20 is divided by 5.
easy
A. 1
B. 2
C. 3
D. 4

Solution

  1. Step 1: Use Fermat’s (or observe cycle):

    For prime 5, 2^4 ≡ 1 (mod 5).

  2. Step 2: Reduce the exponent:

    20 mod 4 = 0, so 2^20 ≡ (2^4)^{5} ≡ 1^{5} ≡ 1 (mod 5).

  3. Final Answer:

    Remainder = 1 → Option A.

  4. Quick Check:

    Since 2^4 = 16 ≡ 1 (mod 5), every 4th power returns remainder 1; 20 is multiple of 4 ✅
Hint: Reduce exponent modulo p-1 for prime p (here 4).
Common Mistakes: Not reducing the exponent by 4 and attempting full power arithmetic.
2. Find the remainder when 3^10 is divided by 7.
easy
A. 1
B. 2
C. 3
D. 4

Solution

  1. Step 1: Use Fermat’s Little Theorem (p = 7):

    For prime 7, a^{6} ≡ 1 (mod 7) when a not divisible by 7.

  2. Step 2: Reduce exponent:

    10 mod 6 = 4, so 3^{10} ≡ 3^{4} (mod 7).

  3. Step 3: Compute 3^4 mod 7:

    3^2 = 9 ≡ 2 (mod 7) → 3^4 ≡ 2^2 = 4 (mod 7).

  4. Final Answer:

    Remainder = 4 → Option D.

  5. Quick Check:

    3^6 ≡ 1, so 3^{10} = 3^6×3^4 ≡ 1×4 = 4 ✅
Hint: Reduce exponent modulo 6 for modulus 7 (p-1).
Common Mistakes: Attempting to compute 3^10 directly instead of reducing exponent first.
3. Find the remainder when 7^100 is divided by 13.
easy
A. 1
B. 3
C. 9
D. 12

Solution

  1. Step 1: Use Fermat’s theorem (p = 13):

    Since 13 is prime, powers repeat every 12: 7^{12} ≡ 1 (mod 13).

  2. Step 2: Reduce exponent:

    100 mod 12 = 4, so 7^{100} ≡ 7^{4} (mod 13).

  3. Step 3: Compute 7^4 mod 13:

    7^2 = 49 ≡ 49 - 39 = 10 (mod 13). Then 7^4 ≡ 10^2 = 100 ≡ 100 - 91 = 9 (mod 13).

  4. Final Answer:

    Remainder = 9 → Option C.

  5. Quick Check:

    Reducing exponent to 4 and squaring gives small numbers; 7^4 = 2401 and 2401 mod 13 = 9 ✅
Hint: Reduce exponent modulo 12 when modulus = 13.
Common Mistakes: Forgetting to reduce exponent and computing huge powers directly.
4. Find the remainder when 5^117 is divided by 13.
medium
A. 1
B. 5
C. 8
D. 12

Solution

  1. Step 1: Use Fermat’s theorem (p = 13):

    For prime 13, a^{12} ≡ 1 (mod 13) when gcd(a,13)=1.

  2. Step 2: Reduce exponent:

    117 mod 12 = 9, so 5^{117} ≡ 5^{9} (mod 13).

  3. Step 3: Compute 5^9 quickly using small powers:

    5^2 = 25 ≡ 12 ≡ -1 (mod 13). Then 5^4 ≡ (5^2)^2 ≡ (-1)^2 = 1. So 5^8 ≡ 1 and 5^9 ≡ 5.

  4. Final Answer:

    Remainder = 5 → Option B.

  5. Quick Check:

    Because 5^4 ≡ 1, powers repeat; 5^9 = 5×(5^4)^2 ≡ 5×1 = 5 ✅
Hint: If a^k ≡ 1 for small k, use that to reduce large exponents further.
Common Mistakes: Not spotting 5^2 ≡ -1 which simplifies higher powers greatly.
5. Find the remainder when 9^1000 is divided by 91.
medium
A. 9
B. 1
C. 0
D. 81

Solution

  1. Step 1: Note modulus factorization and φ(91):

    91 = 7 × 13. φ(91) = 91×(1-1/7)×(1-1/13) = 72.

  2. Step 2: Reduce exponent using Euler (gcd(9,91)=1):

    1000 mod 72 = 64, so 9^{1000} ≡ 9^{64} (mod 91).

    3. Step 3: Use CRT: find residues mod 7 and mod 13 separately.

    1. Modulo 7: 9 ≡ 2 (mod 7). Cycle length 6, 64 mod 6 = 4 → 2^4 = 16 ≡ 2 (mod 7). So residue ≡ 2 (mod 7).
    2. Modulo 13: 9 ≡ 9 (mod 13). Cycle length 12, 64 mod 12 = 4 → 9^2 = 81 ≡ 3 (mod 13), so 9^4 ≡ 3^2 = 9 (mod 13). So residue ≡ 9 (mod 13).

  3. Step 4: Solve CRT: x ≡ 2 (mod 7), x ≡ 9 (mod 13).

    Write x = 2 + 7k. Require 2 + 7k ≡ 9 (mod 13) ⇒ 7k ≡ 7 (mod 13). Inverse of 7 mod 13 is 2 (since 7×2=14≡1), so k ≡ 2×7 ≡ 14 ≡ 1 (mod 13). Thus k = 1 yields x = 2 + 7×1 = 9.

  4. Final Answer:

    Remainder = 9 → Option A.

  5. Quick Check:

    9 ≡ 2 (mod 7) and 9 ≡ 9 (mod 13), so x=9 satisfies both congruences; hence remainder 9 (mod 91) is correct. ✅
Hint: When modulus is composite, reduce exponent by φ(n) then use CRT (mod prime factors) if helpful.
Common Mistakes: Assuming 9^{1000} ≡ 1 just because φ(91) divides something - must reduce exponent and compute residue correctly.

Mock Test

Ready for a challenge?

Take a 10-minute AI-powered test with 10 questions (Easy-Medium-Hard mix) and get instant SWOT analysis of your performance!

10 Questions
5 Minutes