Prime Number
Number Theory
Definition
A prime number is a natural number greater than 1 that has exactly two distinct positive divisors: 1 and itself. In other words, a prime number cannot be formed by multiplying two smaller natural numbers.
Equivalently, a prime number p is a positive integer greater than 1 that is not divisible by any positive integer other than 1 and p.
Formal Definition
A natural number p > 1 is prime if and only if:
∀a ∈ ℕ, a | p ⇒ a = 1 or a = p
Where "a | p" denotes "a divides p" (a is a divisor of p).
List of Prime Numbers
The first 25 prime numbers (all primes less than 100) are:
31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
73, 79, 83, 89, 97
The only even prime number is 2. All other even numbers are divisible by 2 and therefore composite.
Key Properties
- Fundamental Theorem of Arithmetic: Every integer greater than 1 can be uniquely represented as a product of prime numbers (up to ordering).
- Euclid's Theorem: There are infinitely many prime numbers.
- Prime Number Theorem: The number of primes less than n, denoted π(n), is approximately n/ln(n).
- Twin Primes: Pairs of primes that differ by 2, such as (3, 5), (5, 7), (11, 13).
- Mersenne Primes: Primes of the form 2p - 1 where p is prime.
Prime Factorization
Prime factorization is the process of expressing a composite number as a product of prime numbers.
Example: Find the prime factorization of 360.
360 = 2 × 180
180 = 2 × 90
90 = 2 × 45
45 = 3 × 15
15 = 3 × 5
Therefore: 360 = 2³ × 3² × 5
Primality Testing
Several algorithms exist to determine whether a number is prime:
Trial Division
The simplest method: test divisibility by all integers from 2 to √n.
Example: Is 97 prime?
√97 ≈ 9.8, so we test divisibility by primes ≤ 9: 2, 3, 5, 7
97 is odd (not divisible by 2)
9 + 7 = 16, not divisible by 3
Does not end in 0 or 5 (not divisible by 5)
97 ÷ 7 = 13 remainder 6 (not divisible by 7)
Therefore, 97 is prime.
Sieve of Eratosthenes
An ancient algorithm for finding all primes up to a given limit n.
Algorithm:
- Create a list of consecutive integers from 2 to n
- Start with the first number p = 2
- Mark all multiples of p (excluding p itself) as composite
- Find the next unmarked number > p and repeat
- Stop when p² > n
Important Theorems
Fermat's Little Theorem
If p is prime and a is not divisible by p, then:
ap-1 ≡ 1 (mod p)
Fundamental Theorem of Arithmetic
Every n > 1 can be written uniquely as:
n = p₁a₁ × p₂a₂ × ... × pkak
where p₁ < p₂ < ... < pk are primes and ai ≥ 1
Applications
- Cryptography: Prime numbers are fundamental to RSA encryption and modern security systems.
- Hash Functions: Prime numbers are used to create efficient hash tables.
- Random Number Generation: Mersenne primes are used in pseudo-random number generators.
- Computer Science: Many algorithms rely on properties of prime numbers.
- Number Theory: Primes are the building blocks of all integers.
Special Types of Primes
- Twin Primes: (3, 5), (5, 7), (11, 13), (17, 19), ...
- Cousin Primes: Pairs differing by 4: (3, 7), (7, 11), (13, 17), ...
- Sexy Primes: Pairs differing by 6: (5, 11), (7, 13), (11, 17), ...
- Mersenne Primes: 3, 7, 31, 127, 8191, ... (of form 2p-1)
- Fermat Primes: 3, 5, 17, 257, 65537 (of form 22ⁿ+1)
Open Problems
- Goldbach's Conjecture: Every even integer greater than 2 can be expressed as the sum of two primes.
- Twin Prime Conjecture: Are there infinitely many twin primes?
- Riemann Hypothesis: Concerning the distribution of prime numbers.