Number Theory • Topic 1

Prime Numbers

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. Prime numbers are the fundamental building blocks of number theory.

Definition

Definition (Prime Number)

A natural number

p > 1

is prime if its only positive divisors are 1 and

p

A natural number $n > 1$ that is not prime is called composite.

Note

The number 1 is neither prime nor composite by convention.

The First Few Primes

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

Remark

2 is the only even prime. All other even numbers are divisible by 2 and hence composite.

Key Properties

Lemma (Euclid's Lemma)

p

is prime and

p ∣ ab

, then

p ∣ a

p ∣ b

This extends to: if $p ∣ a_{1} a_{2} \dots a_{n}$ , then $p ∣ a_{i}$ for some $i$ .

Theorem (Prime Test)

To check if

n

is prime, we only need to check divisibility by primes up to

n

Proof. If $n = ab$ with $a, b > 1$ , then at least one of $a, b$ must be $\leq n$ .

Suppose both $a > n$ and $b > n$ . Then $ab > n \cdot n = n$ , contradiction. ∎

Infinitude of Primes

Theorem (Euclid's Theorem)

There are infinitely many prime numbers.

Proof. Suppose there are only finitely many primes $p_{1}, p_{2}, \dots, p_{n}$ . Consider:

N = p_{1} p_{2} \dots p_{n} + 1

This number $N$ is not divisible by any $p_{i}$ (since $N \equiv 1 (mod p_{i})$ ).

But $N > 1$ must have a prime divisor, which must be different from all $p_{i}$ . Contradiction. ∎

Types of Primes

Type	Definition	Examples

Twin primes	Primes $p, p + 2$ both prime	$(3, 5), (5, 7), (11, 13)$
Mersenne primes	Primes of form $2^{p} - 1$	$3, 7, 31, 127$
Fermat primes	Primes of form $2^{2^{n}} + 1$	$3, 5, 17, 257, 65537$
Sophie Germain	Prime $p$ where $2 p + 1$ is also prime	$2, 3, 5, 11, 23$

Olympiad Techniques

Finding Prime Factors

Tip (Factorization Patterns)

When a problem involves large numbers, look for patterns:

$n^{2} - 1 = (n - 1) (n + 1)$
$n^{3} - 1 = (n - 1) (n^{2} + n + 1)$
$a^{n} - b^{n}$ has factor $a - b$

Using Primality

Many problems use the fact that primes have exactly two divisors.

Example

Find all primes

p

such that

p^{2} + 2

is prime.

Proof (Solution). For $p = 3$ : $p^{2} + 2 = 11$ ✓ (prime)

For $p \neq = 3$ : We have $p \equiv 1$ or $2 (mod 3)$ , so $p^{2} \equiv 1 (mod 3)$ , meaning $p^{2} + 2 \equiv 0 (mod 3)$ .

Since $p^{2} + 2 > 3$ , it's composite.

Answer: $p = 3$ is the only solution. ∎

Practice Problems

Exercise (Problem 1)

Prove that if

p

and

p^{2} + 2

are both prime, then

p = 3

Exercise (Problem 2)

Find all primes

p

such that

2^{p} + p^{2}

is prime.

Exercise (Problem 3)

Prove that there are infinitely many primes of the form

4 k + 3