0
0

Remainder Theorems (Euler/Fermat)

Introduction

When exponents become very large, direct division to find remainders is inefficient. This is where Euler’s and Fermat’s Theorems are powerful tools. They help simplify modular arithmetic by reducing large exponents based on number properties.

Pattern: Remainder Theorems (Euler/Fermat)

Pattern

Euler’s and Fermat’s theorems simplify finding remainders for large powers by using modular reduction and special exponent rules.

  • Fermat’s Little Theorem (FLT):
    If p is a prime number and a is not divisible by p, then:
    ap-1 ≡ 1 (mod p)
    ⇒ ak mod p = a(k mod (p-1)) mod p
  • Euler’s Theorem (Generalized):
    If a and n are coprime (GCD(a, n) = 1), then:
    aφ(n) ≡ 1 (mod n)
    where φ(n) = number of integers less than n that are coprime to n (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₂) × … for all distinct prime factors of n.
    Example: φ(10) = 10 × (1-1/2) × (1-1/5) = 10×(1/2)×(4/5) = 4
  • Shortcut Relation:
    - If modulus n is prime → use Fermat’s theorem.
    - If modulus n is composite but coprime with base → use Euler’s theorem.
    - If not coprime → split and use Chinese Remainder Theorem or basic modular reduction.

Step-by-Step Example

Question

Find the remainder when 7100 is divided by 13.

Solution

  1. Step 1: Recognize the modulus is prime:

    Since 13 is prime, use Fermat’s Little Theorem: ap-1 ≡ 1 (mod p).

  2. Step 2: Apply theorem:

    712 ≡ 1 (mod 13).

  3. Step 3: Reduce exponent modulo (p-1):

    100 mod 12 = 4. So 7100 ≡ 74 (mod 13).

  4. Step 4: Compute reduced power:

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

  5. Final Answer:

    Remainder = 9.

  6. Quick Check:

    Verified using modular reduction - 7¹² ≡ 1 mod 13, 7⁴ → remainder 9 ✅

Quick Variations

1. When modulus is prime → use Fermat’s theorem.

2. When modulus is composite and coprime with base → use Euler’s theorem.

3. If modulus shares factors with base → split the modulus and use Chinese Remainder Theorem.

4. When exponent is extremely large → reduce the exponent stepwise using φ(n) repeatedly.

Trick to Always Use

  • Step 1: Check if modulus is prime → use Fermat’s theorem.
  • Step 2: If not prime but coprime → use Euler’s theorem (find φ(n)).
  • Step 3: Always reduce exponent mod (p-1) or φ(n).
  • Step 4: Multiply results only modulo n to keep numbers small.

Summary

Summary

  • Fermat’s theorem: ap-1 ≡ 1 (mod p) for prime p.
  • Euler’s theorem: aφ(n) ≡ 1 (mod n) when GCD(a,n)=1.
  • Reduce exponents using (p-1) or φ(n) to simplify calculations.
  • Compute modular powers step-by-step using squaring to avoid large 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