Number Theory
Number theory is the study of integers and their properties.
1. Divisibility
An integer a is divisible by an integer b if there exists an integer k such that a = bk.
Divisibility rules for common numbers (2, 3, 4, 5, 9, 10).
2. Prime Numbers
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and
itself.
The Fundamental Theorem of Arithmetic: Every positive integer can be uniquely factored as a
product of primes.
3. Greatest Common Divisor (GCD) and Least Common Multiple (LCM)
GCD: The largest positive integer that divides both numbers without a remainder.
LCM: The smallest positive integer that is divisible by both numbers.
Euclidean Algorithm: An efficient method for computing the GCD of two numbers.
4. Modular Arithmetic
In modular arithmetic, numbers "wrap around" upon reaching a certain value (the modulus).
Congruence relation: a ≡ b (mod m) if m divides (a - b).
5. Euler's Totient Function
φ(n) counts the number of integers up to n that are coprime to n.
For prime p: φ(p) = p - 1
6. Fermat's Little Theorem
If p is prime and a is not divisible by p, then: a^(p-1) ≡ 1 (mod p)
Number theory has many applications in cryptography and computer science.
