Arithmetic Theorems

Master the most powerful theorems for remainders, divisibility, and modular arithmetic. These tools are essential for CAT, XAT, and other competitive exams!

Key Arithmetic Theorems & Properties

Divisibility rules for quick checks (2, 3, 4, 5, 6, 8, 9, 10, 11, etc.)
Remainder Theorem for polynomials: The remainder when f(x) is divided by (x - a) is f(a).
Euclid's Division Lemma: For any integers a, b (b > 0), a = bq + r, 0 ≤ r < b.
LCM and GCD: For any positive integers a, b: LCM(a, b) × GCD(a, b) = a × b.
Properties of even/odd numbers: Even + Even = Even, Odd × Odd = Odd, etc.
Prime numbers: Only two positive divisors (1 and itself).

Advanced Remainder Theorems (In-Depth)

Fermat's Little Theorem

Statement: If p is a prime number and a is any integer, then a^p ≡ a (mod p). If a and p are coprime, then a^p-1 ≡ 1 (mod p).

When to Use: Use this theorem to quickly find remainders of large powers when divided by a prime, especially when the base and the prime are coprime.

Why It Works: The theorem is rooted in the properties of modular arithmetic and the fact that multiplying all nonzero residues modulo a prime cycles through all possible values.

Step-by-Step Example 1:
Find the remainder when 2²⁵⁶ is divided by 17.

17 is prime, 2 and 17 are coprime.
By Fermat: 2¹⁶ ≡ 1 (mod 17).
256 = 16 × 16, so 2²⁵⁶ = (2¹⁶)¹⁶.
So, (1)¹⁶ ≡ 1 (mod 17).
Final Answer: Remainder is 1.

Step-by-Step Example 2:
Find the remainder when 3⁷⁵ is divided by 37.

37 is prime, 3 and 37 are coprime.
By Fermat: 3³⁶ ≡ 1 (mod 37).
75 = 2×36 + 3, so 3⁷⁵ = (3³⁶)² × 3³.
(1)² × 27 = 27 (mod 37).
Final Answer: Remainder is 27.

Edge Case: If a is a multiple of p, then a^p-1 ≡ 0 (mod p).

Tips & Pitfalls:

Always check if the divisor is prime.
Check if the base and the prime are coprime for the second part.
For composite divisors, use Euler's theorem instead.

Euler's Theorem & Euler's Totient Function

Statement: If a and n are coprime, then a^ϕ(n) ≡ 1 (mod n), where ϕ(n) is the Euler's totient function (the count of numbers less than n that are coprime to n).

How to Compute ϕ(n): For n = p₁^k1 × p₂^k2 × ... × p_m^km (prime factorization),
ϕ(n) = n × (1 - 1/p₁) × (1 - 1/p₂) × ... × (1 - 1/p_m)

When to Use: Use Euler's theorem for large exponents with composite moduli, provided the base and modulus are coprime.

Step-by-Step Example 1:
Find the remainder when 2²⁵⁶ is divided by 15.

2 and 15 are coprime. 15 = 3 × 5.
ϕ(15) = 15 × (1 - 1/3) × (1 - 1/5) = 15 × (2/3) × (4/5) = 8.
2⁸ ≡ 1 (mod 15), so 2²⁵⁶ = (2⁸)³² ≡ 1 (mod 15).
Final Answer: Remainder is 1.

Step-by-Step Example 2:
What are the last two digits of 7²⁰⁰⁸?

Last two digits = remainder when divided by 100.
7 and 100 are coprime. 100 = 2² × 5².
ϕ(100) = 100 × (1 - 1/2) × (1 - 1/5) = 100 × (1/2) × (4/5) = 40.
7⁴⁰ ≡ 1 (mod 100), so 7²⁰⁰⁰ ≡ 1 (mod 100).
7²⁰⁰⁸ = 7²⁰⁰⁰ × 7⁸, so remainder is 7⁸ mod 100 = 01.

Edge Case: If a and n are not coprime, Euler's theorem does not apply.

Tips & Pitfalls:

Always check coprimality before applying Euler's theorem.
For prime moduli, Euler's theorem reduces to Fermat's Little Theorem.
ϕ(n) is always less than n for n > 1.

Wilson's Theorem

Statement: For any prime p, (p-1)! ≡ -1 (mod p), or equivalently, (p-1)! mod p = p-1.

Corollary: (p-2)! mod p = 1 for any prime p.

When to Use: Use Wilson's theorem for factorial remainders with prime divisors.

Step-by-Step Example 1:
Find the remainder when 568! is divided by 569.

569 is prime, so 568! mod 569 = 568.

Step-by-Step Example 2:
Find the remainder when 225! is divided by 227.

227 is prime, so (227-2)! mod 227 = 1, so 225! mod 227 = 1.

Advanced Example:
Find the remainder when 15! is divided by 19.

19 is prime. By the corollary, (19-2)! mod 19 = 1, so 17! mod 19 = 1.
17! = 17 × 16 × 15! ≡ 1 (mod 19).
17 ≡ -2, 16 ≡ -3 (mod 19), so (-2) × (-3) × 15! ≡ 1 (mod 19).
6 × 15! ≡ 1 (mod 19), so 15! ≡ 16 (mod 19).
Final Answer: Remainder is 16.

Tips & Pitfalls:

Only applies to primes.
For (p-2)! mod p, answer is always 1 for prime p.
For large factorials, reduce step by step using modular arithmetic.

Chinese Remainder Theorem (CRT)

Statement: If you know the remainders of a number when divided by several pairwise coprime numbers, you can uniquely determine the remainder when divided by their product.

How to Use:

Break the divisor into coprime factors (e.g., 119 = 17 × 7).
Find the remainder for each factor.
Set up congruences and solve for the original number using the system of equations.

Step-by-Step Example 1:
Find the remainder when 344237 is divided by 119.

119 = 17 × 7 (coprime).
344237 mod 17 = 4, 344237 mod 7 = 1.
Set up: x ≡ 4 (mod 17), x ≡ 1 (mod 7).
Find x that satisfies both. The answer is 106.

Step-by-Step Example 2:
Find the remainder when 4952517 is divided by 78.

78 = 13 × 6 (coprime).
4952517 mod 13 = 1, 4952517 mod 6 = 3.
Set up: x ≡ 1 (mod 13), x ≡ 3 (mod 6).
Find x that satisfies both. The answer is 27.

Tips & Pitfalls:

Only works if divisors are coprime.
For more than two divisors, apply iteratively.
CRT is powerful for reconstructing numbers from modular information.

Ready to Test Your Arithmetic Theorems?

Practice a comprehensive set of Arithmetic Theorems questions, from basics to CAT-level challenges.
Challenge yourself and track your progress!

📐Practice Arithmetic Theorems →