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

1. Natural Numbers: All positive integers starting from 1: N = {1, 2, 3, ...}.
2. Whole Numbers: Natural numbers including zero: W = {0, 1, 2, 3, ...}.
3. Integers: All positive and negative whole numbers, including zero: Z = {..., -3, -2, -1, 0, 1, 2, 3, ...}.
4. 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=p_1^{a_1}\times p_2^{a_2}\times ...\times p_k^{a_k},$ 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 $2^{100}$ mod 13.

• $2^{12}$≡ 1 (mod 13), so $2^{96}$ ≡ 1 (mod 13)
• $2^{100}=2^{96}\times 2^4$ ≡ 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