Prime Numbers

Last updated: December 2024

Disclaimer: These are my personal notes compiled for my own reference and learning. They may contain errors, incomplete information, or personal interpretations. While I strive for accuracy, these notes are not peer-reviewed and should not be considered authoritative sources. Please consult official textbooks, research papers, or other reliable sources for academic or professional purposes.

1. Definition

A prime number is a natural number $p > 1$ that has exactly two positive divisors: 1 and itself.

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

Note: 1 is not considered prime by modern definition.

2. Fundamental Theorem of Arithmetic

Every integer $n > 1$ can be uniquely factored into prime powers:

$$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$.

3. Euclid's Theorem

There are infinitely many primes.

Proof sketch: Assume finite set $\{p_1, p_2, \ldots, p_k\}$ contains all primes. Consider $N = p_1 p_2 \cdots p_k + 1$. This number is not divisible by any $p_i$, so either $N$ is prime or has a prime factor not in our set.

4. Prime Number Theorem

The number of primes less than or equal to $x$, denoted $\pi(x)$, is asymptotically:

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

More precisely:

$$\lim_{x \to \infty} \frac{\pi(x)}{x/\ln x} = 1$$

5. Sieve of Eratosthenes

Ancient algorithm to find all primes up to $n$:

  1. List numbers from 2 to $n$
  2. Start with smallest unmarked number (initially 2)
  3. Mark all multiples of this number
  4. Repeat until you've processed all numbers up to $\sqrt{n}$

6. Primality Tests

6.1 Trial Division

To test if $n$ is prime, check divisibility by all primes up to $\sqrt{n}$.

6.2 Fermat's Little Theorem Test

If $p$ is prime and $a$ is not divisible by $p$, then:

$$a^{p-1} \equiv 1 \pmod{p}$$

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

6.3 Miller-Rabin Test

Probabilistic primality test based on properties of strong pseudoprimes.

7. Special Types of Primes

7.1 Mersenne Primes

Primes of the form $M_p = 2^p - 1$ where $p$ is prime.

Examples: $M_2 = 3$, $M_3 = 7$, $M_5 = 31$, $M_7 = 127$

7.2 Fermat Primes

Primes of the form $F_n = 2^{2^n} + 1$.

Known Fermat primes: $F_0 = 3$, $F_1 = 5$, $F_2 = 17$, $F_3 = 257$, $F_4 = 65537$

7.3 Twin Primes

Pairs of primes that differ by 2: $(p, p+2)$.

Examples: (3,5), (5,7), (11,13), (17,19), (29,31), (41,43)

8. Prime Gaps

The gap between consecutive primes $p_n$ and $p_{n+1}$ is $g_n = p_{n+1} - p_n$.

Bertrand's Postulate: For $n > 1$, there's always a prime between $n$ and $2n$.

9. Riemann Hypothesis

The Riemann zeta function is defined for $\text{Re}(s) > 1$ as:

$$\zeta(s) = \sum_{n=1}^{\infty} \frac{1}{n^s} = \prod_{p \text{ prime}} \frac{1}{1-p^{-s}}$$

Riemann Hypothesis: All non-trivial zeros of $\zeta(s)$ have real part $\frac{1}{2}$.

10. Applications

10.1 Cryptography

RSA encryption relies on the difficulty of factoring large composite numbers into their prime factors.

10.2 Hash Functions

Large primes are used in hash table implementations to minimize collisions.

11. Code Example

# Python code for prime number operations
import math

def is_prime(n):
    """Check if n is prime using trial division"""
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        if n % i == 0:
            return False
    return True

def sieve_of_eratosthenes(n):
    """Find all primes up to n"""
    sieve = [True] * (n + 1)
    sieve[0] = sieve[1] = False
    
    for i in range(2, int(math.sqrt(n)) + 1):
        if sieve[i]:
            for j in range(i*i, n + 1, i):
                sieve[j] = False
    
    return [i for i in range(2, n + 1) if sieve[i]]

def prime_factorization(n):
    """Find prime factorization of n"""
    factors = []
    d = 2
    while d * d <= n:
        while n % d == 0:
            factors.append(d)
            n //= d
        d += 1
    if n > 1:
        factors.append(n)
    return factors

def fermat_test(n, a=2):
    """Fermat primality test"""
    if n <= 1:
        return False
    return pow(a, n-1, n) == 1

# Examples
print(f"First 20 primes: {sieve_of_eratosthenes(71)}")
print(f"Is 97 prime? {is_prime(97)}")
print(f"Prime factorization of 60: {prime_factorization(60)}")
print(f"Fermat test for 97: {fermat_test(97)}")

12. References