Number Theory
Number Theory is the study of integers and their properties. It is a foundational part of mathematics with applications in cryptography, computer science, and problem-solving. For JEE aspirants, mastering Number Theory enhances logical reasoning and prepares you for a variety of advanced math problems.
1.0Sets of Numbers
- Natural Numbers: All positive integers starting from 1: N = {1, 2, 3, ...}.
- Whole Numbers: Natural numbers including zero: W = {0, 1, 2, 3, ...}.
- Integers: All positive and negative whole numbers, including zero: Z = {..., -3, -2, -1, 0, 1, 2, 3, ...}.
- Rational and Irrational Numbers
- Rational: Numbers expressible as p/q, where p and q are integers, q ≠ 0.
- Irrational: Numbers not expressible as a ratio of integers (e.g., √2, π).
2.0Prime Numbers and Composite Numbers
Properties of Primes
- Prime Number: Natural number >1 divisible only by 1 and itself.
- Smallest Prime: 2 (also the only even prime).
- Composite Number: Natural number >1 that is not prime.
Distribution of Primes
- Infinite number of primes (proved by Euclid).
- Any integer >1 is either prime or can be factored into primes.
3.0Divisibility and Division Algorithm
Divisibility Rules
- By 2: Last digit is even.
- By 3: Sum of digits divisible by 3.
- By 5: Last digit is 0 or 5.
- Other rules apply for different divisors.
Euclid’s Division Lemma: For any integers a and b (b > 0), there exist unique integers q and r such that: a = bq + r, where 0 ≤ r < b.
4.0Greatest Common Divisor (GCD) and Least Common Multiple (LCM)
Finding GCD: Euclidean Algorithm
To find GCD of a and b:
- Divide a by b, get remainder r.
- Replace a with b, b with r. Repeat until r = 0.
- GCD is the last non-zero remainder.
Relationship Between LCM and GCD
For any two positive integers a and b: LCM(a, b) × GCD(a, b) = a × b
5.0Fundamental Theorem of Arithmetic
Unique Factorization
Every integer greater than 1 can be uniquely written as a product of primes, up to the order of the factors.
Example: 84 = 2² × 3 × 7
Factorization Examples
- 360 = 2³ × 3² × 5
- 210 = 2 × 3 × 5 × 7
6.0Important Theorems in Number Theory
- Fermat’s Little Theorem: If p is a prime number and a is not divisible by p, a^(p-1) ≡ 1 (mod p)
- Euler’s Theorem: If a and n are coprime, a^φ(n) ≡ 1 (mod n) where φ(n) is Euler’s totient function.
- Wilson’s Theorem: A number p > 1 is prime if and only if (p-1)! ≡ -1 (mod p)
7.0Modular Arithmetic
Basic Concepts
- Congruence: a ≡ b (mod n) means n divides (a-b).
- Reduces large numbers in calculations.
- Used in clock arithmetic, cryptography, and JEE-level problems.
Applications
- Remainders in division, cyclic patterns, cryptography, error detection.
8.0Arithmetic Functions
Euler’s Totient Function (φ(n))
Counts the number of integers ≤ n that are coprime to n.
If n=p1a1×p2a2×...×pkak, then
φ(n) = n(1 - 1/p₁)(1 - 1/p₂)...(1 - 1/pₖ)
Number of Divisors and Sum of Divisors
If n = p₁^{a₁} × p₂^{a₂} × ... × pₖ^{aₖ}:
- Number of divisors (d(n)) = (a₁+1)(a₂+1)...(aₖ+1)
- Sum of divisors (σ(n)) = [(p₁^{a₁+1} - 1)/(p₁-1)] × ...
9.0Solved Examples on Number Theory
Example 1: Find the GCD of 180 and 144.
- 180 ÷ 144 = 1, remainder = 36
- 144 ÷ 36 = 4, remainder = 0
- GCD = 36
Example 2: Use Fermat’s Little Theorem to compute 2100 mod 13.
- 212≡ 1 (mod 13), so 296 ≡ 1 (mod 13)
- 2100=296×24 ≡ 1 × 16 ≡ 3 (mod 13)
Example 3: Find the number of divisors of 108.
- 108 = 2² × 3³
- Divisors: (2+1)(3+1) = 3×4 = 12
Example 4: If n = 15, find φ(n).
- 15 = 3×5
- φ(15) = 15 × (1-1/3) × (1-1/5) = 15 × (2/3) × (4/5) = 8