Essential Number Theory Definitions
Prime Numbers
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.
Composite Numbers
A composite number is a positive integer that has at least one positive divisor other than 1 and itself.
Greatest Common Divisor (GCD)
The largest positive integer that divides each of the integers with no remainder.
Least Common Multiple (LCM)
The smallest positive integer that is divisible by each of the integers.
Modular Arithmetic
a ≡ b (mod n) means n divides (a - b)
Equivalently: a and b have the same remainder when divided by n
Perfect Numbers
- Perfect: Sum of proper divisors equals the number (e.g., 6 = 1+2+3)
- Abundant: Sum of proper divisors exceeds the number
- Deficient: Sum of proper divisors is less than the number
Important Number Theory Theorems
Fundamental Theorem of Arithmetic
Every integer greater than 1 can be represented uniquely as a product of prime numbers.
Euclid's Theorem
There are infinitely many prime numbers.
Fermat's Little Theorem
If p is prime and a is not divisible by p, then a^(p-1) ≡ 1 (mod p).
Wilson's Theorem
p is prime if and only if (p-1)! ≡ -1 (mod p).
Chinese Remainder Theorem
System of congruences with pairwise coprime moduli has a unique solution modulo their product.
Euler's Theorem
If gcd(a,n) = 1, then a^φ(n) ≡ 1 (mod n), where φ is Euler's totient function.
GCD and LCM Properties
gcd(a,b) × lcm(a,b) = a × b
gcd(a,b) = gcd(b, a mod b) (Euclidean Algorithm)
lcm(a,b) = |a × b| / gcd(a,b)
Number Theory Algorithms
Sieve of Eratosthenes (Finding Primes)
- Create a list of consecutive integers from 2 through n
- Start with the first number in the list (2)
- Mark all multiples of this number (except the number itself)
- Find the next unmarked number and repeat
- Continue until you've processed all numbers ≤ √n
Euclidean Algorithm (GCD)
gcd(a, b) = gcd(b, a mod b)
Continue until remainder is 0
Extended Euclidean Algorithm
Finds integers x, y such that ax + by = gcd(a, b)
Used for finding modular inverses
Fast Modular Exponentiation
- Use binary representation of exponent
- Square and multiply technique
- Reduces O(n) to O(log n) operations
Primality Testing
- Trial Division: Check divisibility up to √n
- Fermat Test: Probabilistic test using Fermat's Little Theorem
- Miller-Rabin: More reliable probabilistic test
- AKS: Deterministic polynomial-time algorithm
Worked Examples
Example 1: Euclidean Algorithm for GCD
Problem: Find gcd(252, 198)
Solution:
• 252 = 198 × 1 + 54
• 198 = 54 × 3 + 36
• 54 = 36 × 1 + 18
• 36 = 18 × 2 + 0
Answer: gcd(252, 198) = 18
Example 2: Prime Factorization
Problem: Find the prime factorization of 360
Solution:
• 360 ÷ 2 = 180
• 180 ÷ 2 = 90
• 90 ÷ 2 = 45
• 45 ÷ 3 = 15
• 15 ÷ 3 = 5
• 5 ÷ 5 = 1
Answer: 360 = 2³ × 3² × 5
Example 3: Modular Arithmetic
Problem: Calculate 7³ (mod 5)
Solution:
• 7³ = 343
• 343 ÷ 5 = 68 remainder 3
• Therefore: 7³ ≡ 3 (mod 5)
Alternative (using properties):
• 7 ≡ 2 (mod 5)
• 7³ ≡ 2³ ≡ 8 ≡ 3 (mod 5)
Example 4: Finding Modular Inverse
Problem: Find the inverse of 3 (mod 7)
Solution using Extended Euclidean Algorithm:
• Need to find x such that 3x ≡ 1 (mod 7)
• 7 = 3 × 2 + 1
• 1 = 7 - 3 × 2
• Therefore: 1 ≡ -3 × 2 ≡ 3 × 5 (mod 7)
Answer: 3⁻¹ ≡ 5 (mod 7)