0
0

Remainder Theorems (Euler/Fermat)

Introduction

exponent-கள் மிகவும் பெரியதாக இருந்தால், நேரடியாக division செய்து remainder கண்டறிவது செயல்திறன் குறைவானது. அப்போது Euler’s மற்றும் Fermat’s Theorems மிகப் பயனுள்ள கருவிகளாகும். இவை எண்களின் பண்புகளைப் பயன்படுத்தி பெரிய exponent-களை குறைத்து, modular arithmetic ஐ எளிதாக்க உதவுகின்றன.

Pattern: Remainder Theorems (Euler/Fermat)

Pattern

Euler’s மற்றும் Fermat’s theorems, modular reduction மற்றும் சிறப்பு exponent விதிகளைப் பயன்படுத்தி, பெரிய powers-க்கான remainders-ஐ எளிதாகக் கண்டறிய உதவுகின்றன.

  • Fermat’s Little Theorem (FLT):
    p ஒரு prime எண் ஆகவும், a என்பது p-ஆல் வகுபடாததாகவும் இருந்தால்:
    ap-1 ≡ 1 (mod p)
    ⇒ ak mod p = a(k mod (p-1)) mod p
  • Euler’s Theorem (Generalized):
    a மற்றும் n ஆகியவை coprime (GCD(a, n) = 1) ஆக இருந்தால்:
    aφ(n) ≡ 1 (mod n)
    இங்கு φ(n) = n-ஐ விட சிறியதாகவும் n-க்கு coprime ஆகவும் உள்ள முழு எண்களின் எண்ணிக்கை (Euler’s Totient Function).
    ⇒ ak mod n = a(k mod φ(n)) mod n
  • Euler’s Totient Function φ(n):
    φ(n) = n × (1 - 1/p₁) × (1 - 1/p₂) × … (n-ன் அனைத்து distinct prime factors களுக்கும்).
    Example: φ(10) = 10 × (1-1/2) × (1-1/5) = 10×(1/2)×(4/5) = 4
  • Shortcut Relation:
    - modulus n prime ஆக இருந்தால் → Fermat’s theorem பயன்படுத்துங்கள்.
    - modulus n composite ஆனால் base-உடன் coprime ஆக இருந்தால் → Euler’s theorem பயன்படுத்துங்கள்.
    - coprime இல்லை என்றால் → modulus-ஐப் பிரித்து Chinese Remainder Theorem அல்லது அடிப்படை modular reduction பயன்படுத்துங்கள்.

Step-by-Step Example

Question

7100 என்பதை 13-ஆல் வகுத்தால் கிடைக்கும் remainder ஐ கண்டறியுங்கள்.

Solution

  1. Step 1: Modulus prime என்பதை கவனியுங்கள்:

    13 ஒரு prime எண் என்பதால், Fermat’s Little Theorem பயன்படுத்தலாம்: ap-1 ≡ 1 (mod p).

  2. Step 2: Theorem பயன்படுத்துதல்:

    712 ≡ 1 (mod 13).

  3. Step 3: Exponent-ஐ (p-1) modulo-ஆகக் குறைத்தல்:

    100 mod 12 = 4. ஆகவே 7100 ≡ 74 (mod 13).

  4. Step 4: குறைக்கப்பட்ட power-ஐ கணக்கிடுதல்:

    72 = 49 → 49 mod 13 = 10.
    74 = (72)² = 10² = 100 → 100 mod 13 = 9.

  5. Final Answer:

    Remainder = 9.

  6. Quick Check:

    modular reduction மூலம் சரிபார்க்கப்பட்டது - 7¹² ≡ 1 (mod 13), 7⁴ → remainder 9 ✅

Quick Variations

1. modulus prime ஆக இருந்தால் → Fermat’s theorem பயன்படுத்துங்கள்.

2. modulus composite மற்றும் base-உடன் coprime ஆக இருந்தால் → Euler’s theorem பயன்படுத்துங்கள்.

3. modulus, base-உடன் factors பகிர்ந்தால் → modulus-ஐப் பிரித்து Chinese Remainder Theorem பயன்படுத்துங்கள்.

4. exponent மிக மிக பெரியதாக இருந்தால் → φ(n) பயன்படுத்தி exponent-ஐ படிப்படியாகக் குறைக்கவும்.

Trick to Always Use

  • Step 1: modulus prime ஆா என்பதைச் சரிபார்க்கவும் → Fermat’s theorem.
  • Step 2: prime இல்லை ஆனால் coprime என்றால் → Euler’s theorem (φ(n) கண்டறியவும்).
  • Step 3: exponent-ஐ எப்போதும் (p-1) அல்லது φ(n) modulo-ஆகக் குறைக்கவும்.
  • Step 4: எண்கள் பெரிதாகாமல் இருக்க, முடிவுகளை n modulo-வில் மட்டுமே பெருக்கவும்.

Summary

Summary

  • Fermat’s theorem: prime p க்கு ap-1 ≡ 1 (mod p).
  • Euler’s theorem: GCD(a,n)=1 என்றால் aφ(n) ≡ 1 (mod n).
  • (p-1) அல்லது φ(n) பயன்படுத்தி exponents-ஐக் குறைத்து கணக்குகளை எளிமைப்படுத்துங்கள்.
  • பெரிய எண்களைத் தவிர்க்க modular powers-ஐ படிப்படியாக (squaring) கணக்கிடுங்கள்.

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