Difficulty: Introductory | Prerequisites: Basic integer arithmetic (divisibility, factors, multiples)
Prime numbers are the atoms of the integers: every whole number greater than 1 is either prime itself or built by multiplying primes together. This topic sits at the start of number theory and underpins modern cryptography, computer science, and algebra. You need to be comfortable with divisibility (what it means for one integer to divide another) and basic arithmetic. If you are unsure what "a divides b" means, review that first.
A prime number is a positive integer greater than 1 whose only divisors are 1 and itself. The Fundamental Theorem of Arithmetic guarantees that every integer greater than 1 has a unique prime factorisation. This uniqueness is what makes primes so powerful in both pure mathematics and applied cryptography.
Prime number
A positive integer greater than 1 that has no positive integer divisors other than 1 and itself. Think of it as a number that cannot be broken into smaller whole-number factors; it is indivisible in the multiplicative sense.
Composite number
A positive integer greater than 1 that is not prime, meaning it has at least one divisor other than 1 and itself. In simple terms, it can be written as a product of two smaller positive integers.
Prime factorisation
The expression of a positive integer as a product of prime numbers. For example, 60 = 2² × 3 × 5. Think of it as dismantling a number down to its prime building blocks.
Fundamental Theorem of Arithmetic
Every positive integer greater than 1 can be expressed as a product of primes in exactly one way (up to the order of the factors). In simple terms, there is only one recipe of prime ingredients for each number, which is why we can rely on factorisation as a definitive property of a number.
Divisor (factor)
An integer d is a divisor of n if n / d is also an integer (i.e., d divides n with no remainder). In simple terms, d fits into n a whole number of times.
A prime p satisfies: p > 1, and the only positive divisors of p are 1 and p
The first several primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ...
2 is the only even prime; every other even number is divisible by 2 and therefore composite
1 is not a prime (by convention and for good mathematical reasons, primarily to preserve the uniqueness of prime factorisation)
To check if n is prime, test divisibility by all primes up to √n
If none of them divide n, then n is prime
You only need to check up to √n because if n = a × b with both a, b > 1, at least one of a or b must be ≤ √n
For large numbers, more sophisticated algorithms exist (Miller-Rabin, AKS), but the trial division method is the conceptual foundation
Statement: every integer n > 1 can be written as n = p1^e1 × p2^e2 × ... × pk^ek, where p1, p2, ..., pk are distinct primes and e1, e2, ..., ek are positive integers
The factorisation is unique up to the order of the factors
12 = 2² × 3, and there is no other way to express 12 as a product of primes
Uniqueness is the key property. Without it, much of number theory and algebra would collapse
The theorem has two parts: existence (a factorisation always exists) and uniqueness (there is only one such factorisation)
There are infinitely many primes
Euclid's proof (by contradiction): suppose there are finitely many primes p1, p2, ..., pn. Consider N = p1 × p2 × ... × pn + 1. N is not divisible by any of the listed primes (it leaves remainder 1), so either N is prime or it has a prime factor not on the list. Either way, the original list was incomplete.
Prime factorisation (general form): n = p1^e1 × p2^e2 × ... × pk^ek
Trial division bound: To test whether n is prime, check divisibility by all primes p ≤ √n
Euclid's construction (proof of infinitude): N = p1 × p2 × ... × pn + 1
RSA encryption, the backbone of secure internet communication, relies on the difficulty of factoring large numbers into primes. Multiplying two large primes together is fast; reversing the process (finding the factors given only the product) is computationally infeasible for sufficiently large numbers. Hash functions and digital signatures also draw on number-theoretic properties of primes.
Students often think 1 is a prime number. It is not. Excluding 1 from the primes is necessary to make the Fundamental Theorem of Arithmetic work (otherwise factorisations would not be unique, since you could always multiply by additional factors of 1).
Some students believe that the number N in Euclid's proof must itself be prime. It need not be; the point is that N has a prime factor not already on the list.
Students sometimes assume that all odd numbers are prime. Odd composite numbers are plentiful (9, 15, 21, 25, 27, ...).
The Fundamental Theorem of Arithmetic applies to integers greater than 1. Students occasionally try to "factorise" 0 or 1, which falls outside the theorem's scope.
⚠️ Expect to be asked to find the prime factorisation of a given integer and to use it (e.g., to find the GCD or LCM of two numbers).
⚠️ The proof that there are infinitely many primes (Euclid's argument) is a classic exam question. Know the structure of the proof by contradiction.
⚠️ Be prepared to explain why 1 is not considered prime, with reference to the Fundamental Theorem of Arithmetic.
True or false: 1 is a prime number.
Fill in the blank: To check if 97 is prime by trial division, you only need to test primes up to ___.
True or false: The prime factorisation of an integer greater than 1 is unique.
Fill in the blank: 2 is the only ___ prime number.
True or false: In Euclid's proof of the infinitude of primes, the number N = p1 × p2 × ... × pn + 1 is always prime.
Answers: 1. False. 2. √97 ≈ 9.8, so primes up to 9 (i.e., 2, 3, 5, 7). 3. True (up to order of factors). 4. Even. 5. False (N might be composite, but it has a prime factor not on the list).
Q: Find the prime factorisation of 180.
A: 180 = 2 × 90 = 2 × 2 × 45 = 2² × 9 × 5 = 2² × 3² × 5.
Q: Use the Fundamental Theorem of Arithmetic to find the GCD of 60 and 84.
A: 60 = 2² × 3 × 5. 84 = 2² × 3 × 7. The GCD takes the minimum exponent of each shared prime: GCD = 2² × 3 = 12.
Q: Outline Euclid's proof that there are infinitely many primes.
A: Assume for contradiction that there are only finitely many primes: p1, p2, ..., pn. Construct N = p1 × p2 × ... × pn + 1. Since N leaves remainder 1 when divided by any pi, none of the listed primes divides N. So either N is itself a new prime, or N has a prime factor outside the list. In either case, the list is incomplete, contradicting the assumption.
Q: Why is the number 1 excluded from the set of prime numbers?
A: If 1 were considered prime, prime factorisations would not be unique, because you could always insert extra factors of 1. The Fundamental Theorem of Arithmetic requires uniqueness, and excluding 1 preserves it.
Prime numbers connect to modular arithmetic (primes define the fields Z/pZ), to cryptography (RSA, Diffie-Hellman), and to analytic number theory (the distribution of primes, the Prime Number Theorem, the Riemann Hypothesis). Within this course, prime factorisation is also the basis for computing greatest common divisors and least common multiples.
prime number, composite number, prime factorisation, Fundamental Theorem of Arithmetic, unique factorisation, Euclid's proof, infinitude of primes, trial division, divisibility, GCD, LCM, RSA encryption, modular arithmetic, number theory, sieve of Eratosthenes, prime testing, MATH 101