Prime Numbers

Definition

A prime number is an integer $p > 1$ whose only positive divisors are 1 and $p$.

A composite number is an integer $n > 1$ that is not prime (has divisors other than 1 and itself).

First Few Primes

$2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, \ldots$

Note: 1 is neither prime nor composite by convention.

Fundamental Theorem of Arithmetic

Every integer $n > 1$ can be written uniquely (up to order) as a product of primes: $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$

where $p_1 < p_2 < \cdots < p_k$ are primes and $a_i \geq 1$.

Examples

• $60 = 2^2 \cdot 3 \cdot 5$
• $100 = 2^2 \cdot 5^2$
• $360 = 2^3 \cdot 3^2 \cdot 5$

Properties of Primes

Euclid's Lemma

If $p$ is prime and $p \mid ab$, then $p \mid a$ or $p \mid b$.

Infinitude of Primes

There are infinitely many primes.

Proof (Euclid): Suppose primes are $p_1, \ldots, p_n$ (finite list). Consider $N = p_1 p_2 \cdots p_n + 1$. $N$ is not divisible by any $p_i$ (leaves remainder 1). So $N$ is either prime or has a prime factor not in the list. Contradiction! $\square$

Sieve of Eratosthenes

Algorithm to find all primes up to $n$:

1. List integers from 2 to $n$
2. Start with smallest unmarked number $p$
3. Mark all multiples of $p$ (except $p$ itself)
4. Repeat from step 2 until $p > \sqrt{n}$
5. Unmarked numbers are prime

Example (up to 30)

Start: 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30

Cross out multiples of 2: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30

Cross out multiples of 3: 9, 15, 21, 27

Cross out multiples of 5: 25

Primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29

Time Complexity

$O(n \log \log n)$

Prime Factorization

Trial Division

Test divisibility by primes up to $\sqrt{n}$:

factor(n):
    for p = 2, 3, 5, 7, 11, ... up to √n:
        while p divides n:
            output p
            n = n / p
    if n > 1:
        output n  # remaining prime factor

Using Prime Factorization

For $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$:

Number of divisors: $\tau(n) = (a_1 + 1)(a_2 + 1) \cdots (a_k + 1)$

Sum of divisors: $\sigma(n) = \frac{p_1^{a_1+1} - 1}{p_1 - 1} \cdot \frac{p_2^{a_2+1} - 1}{p_2 - 1} \cdots \frac{p_k^{a_k+1} - 1}{p_k - 1}$

GCD and LCM: $\gcd(m, n) = \prod p_i^{\min(a_i, b_i)}$ $\text{lcm}(m, n) = \prod p_i^{\max(a_i, b_i)}$

Primality Testing

Trial Division

Test divisibility by all primes $\leq \sqrt{n}$. Time: $O(\sqrt{n})$

Fermat Primality Test

If $n$ is prime and $\gcd(a, n) = 1$, then $a^{n-1} \equiv 1 \pmod{n}$.

If $a^{n-1} \not\equiv 1 \pmod{n}$, then $n$ is composite.

Problem: Carmichael numbers pass this test but are composite.

Miller-Rabin Test

Probabilistic test, more reliable than Fermat. Used in practice for large numbers.

AKS Primality Test

Deterministic polynomial-time algorithm (2002). Proves P = NP is not needed for primality testing.

Prime Number Theorem

$\pi(n) \sim \frac{n}{\ln n}$

where $\pi(n)$ = number of primes $\leq n$.

Consequences

• Average gap between consecutive primes near $n$ is about $\ln n$
• The $n$-th prime is approximately $n \ln n$

Special Types of Primes

Type	Definition	Examples
Twin primes	Differ by 2	(3,5), (5,7), (11,13)
Mersenne primes	Form $2^p - 1$	3, 7, 31, 127
Fermat primes	Form $2^{2^n} + 1$	3, 5, 17, 257, 65537
Sophie Germain	$p$ and $2p+1$ both prime	2, 3, 5, 11

Open Problems

• Twin Prime Conjecture: Infinitely many twin primes
• Goldbach's Conjecture: Every even $n > 2$ is sum of two primes
• Are there infinitely many Mersenne primes?