Prime Numbers — Mathematics Knowledge System

Overview

A prime number is a natural number greater than 1 whose only positive divisors are 1 and itself — it cannot be written as a product of two smaller natural numbers. 2, 3, 5, 7, 11, 13, … are prime; numbers like 4, 6, 9 that do factor are called composite. Primes are the multiplicative 'atoms' of arithmetic: every whole number greater than 1 is a prime or a unique product of primes. There are infinitely many of them, a fact known since Euclid.

Intuition

Think of building numbers by multiplication. Some numbers can be broken into smaller factors — 12 = 3 × 4 — but you eventually reach numbers that refuse to break: 2, 3, 5, 7. Those are the primes, the indivisible building blocks. Just as molecules are made of atoms in exactly one way, every whole number is made of primes in exactly one way — this is the Fundamental Theorem of Arithmetic.

Formal Definition

Definition

A natural number p > 1 is prime if its only positive divisors are 1 and p. Equivalently, p is prime if whenever p divides a product ab, it divides a or b.

p > 1 \text{ prime} \iff (d \mid p \Rightarrow d = 1 \text{ or } d = p)

Definition

Notation

Notation	Meaning
$p$	Conventionally denotes a prime number
$a \mid b$	a divides b (b is a multiple of a)
$\pi(x)$	The prime-counting function — how many primes are ≤ x

Properties

Example factorization of 50

50 = 2 \cdot 5^2

Example factorization of 12

12 = 2^2 \cdot 3

Not-prime Euclid number

1 + 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 = 30031

Applications

RSA public-key cryptography relies on multiplying two large primes being easy while factoring the product back is computationally infeasible.

Worked Examples

Test small divisors. 51 = 3 × 17, so it has divisors other than 1 and itself.
$51 = 3 \cdot 17$

Answer: No — 51 = 3 × 17 is composite.

Practice Problems

Difficulty 2/10

Which of these is prime?

21272933

Difficulty 3/10

Factor 90 into primes.

Difficulty 4/10

Why is 1 not considered prime?

Common Mistakes

Common Mistake

Thinking 1 is prime.

1 is neither prime nor composite. Primes are defined as > 1, so that every integer has a UNIQUE prime factorization.

Common Mistake

Thinking all odd numbers are prime.

9, 15, 21, 25 are odd but composite. And 2 is the only even prime. Oddness and primality are different.

Quiz

Flashcards

1 / 3

Historical Background

Euclid proved around 300 BCE that there are infinitely many primes and that every integer factors uniquely into primes. The study of how primes are distributed drove centuries of mathematics, culminating in the Prime Number Theorem (1896) and the still-unsolved Riemann Hypothesis. Since the 1970s, the difficulty of factoring large numbers into primes has underpinned public-key cryptography.

c. 300 BCE
Euclid proves the infinitude of primes and unique factorization
Euclid
1896
Hadamard and de la Vallée Poussin prove the Prime Number Theorem
Jacques Hadamard, Charles Jean de la Vallée Poussin
1977
RSA turns the hardness of prime factorization into public-key cryptography
Rivest, Shamir, Adleman

Summary

A prime is a natural number > 1 with no divisors other than 1 and itself.
Primes are the multiplicative building blocks: every integer > 1 factors uniquely into primes.
There are infinitely many primes (Euclid).
2 is the only even prime; 1 is neither prime nor composite.
Prime factorization's difficulty underpins modern cryptography.

References

BookHardy, G.H. & Wright, E.M. An Introduction to the Theory of Numbers, 6th ed.
WebsiteWikipedia — Prime number