Learn first: Divisibility rules, GCD and LCM
Primes are the "atoms" of the natural numbers: every number is built from them as a product in exactly one way. Counting divisors, summing divisors, the GCD (greatest common divisor) and the LCM (least common multiple) all start from prime factorisation. Primes also underpin modern encryption (for example, secure internet connections), which relies on the fact that factorising a large number into primes is very hard. This lesson covers the definitions, primality testing, the fundamental theorem of arithmetic, divisor formulas and typical olympiad-style problems.
There are 25 primes below 100: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
Why is 1 not prime? Otherwise factorisation would not be unique: 6 = 2·3 = 1·2·3 = 1·1·2·3. The definition is chosen precisely so that the fundamental theorem works.
Apart from 2 and 5, primes end in the digits 1, 3, 7, 9; every prime greater than 3 has the form 6k ± 1 (numbers 6k, 6k ± 2, 6k + 3 are divisible by 2 or 3).
To check whether n is prime it is enough to try dividing it by the primes not exceeding √n. Reason: if n = a·b with a ≤ b, then a · a ≤ a · b = n, so a ≤ √n. Hence a composite number always has a divisor no larger than √n.
The sieve of Eratosthenes: write the numbers from 2 to n and cross out the multiples of 2, 3, 5, … in turn (but not the numbers themselves); what remains are the primes. You can stop once you reach a prime greater than √n: every number not yet crossed out is prime.
Divisibility tests speed things up: by 2 — the last digit is even; by 3 — the digit sum is divisible by 3; by 5 — the last digit is 0 or 5; by 11 — the difference between the sums of alternate digits is divisible by 11.
Is 221 prime?
Every natural number greater than 1 factorises into primes in exactly one way (up to order):
n = p₁^a₁ · p₂^a₂ · … · p_k^a_k
Method: keep dividing by the smallest prime divisor.
360 = 2·180 = 2·2·90 = 2·2·2·45 = 2³·3²·5.
There are infinitely many primes (Euclid). Suppose there were finitely many: p₁, p₂, …, p_k. Consider N = p₁p₂…p_k + 1. It is divisible by none of the pᵢ (remainder 1). But N > 1 has some prime divisor — so there is a prime missing from the list. Contradiction.
Note: N itself need not be prime: 2·3·5·7·11·13 + 1 = 30031 = 59·509. The proof only shows that a prime divisor outside the list exists.
Number of divisors: τ(n) = (a₁ + 1)(a₂ + 1)…(a_k + 1)
Sum of divisors: σ(n) = (1 + p₁ + … + p₁^a₁)(1 + p₂ + … + p₂^a₂)…
Why? Each divisor has the form p₁^b₁·p₂^b₂…, where b₁ can be chosen from 0, 1, …, a₁ — a₁ + 1 options; the choices are independent, so they multiply. Expanding the brackets in the sum formula produces every divisor exactly once.
How many natural divisors does 360 have, and how many of them are odd?
Factorise both numbers into primes:
GCD — product of the common primes to their lowest powers
LCM — product of all primes that occur, to their highest powers
GCD(a, b) · LCM(a, b) = a · b
The last formula holds because for each prime min + max equals the sum of the two exponents.
Find the GCD and the LCM of 360 and 84.
a and b are coprime if they share no prime factor (GCD = 1). Consecutive natural numbers are always coprime: a common divisor must also divide their difference, which is 1.
Twin primes differ by 2: (3, 5), (5, 7), (11, 13), …. The only triple with p, p + 2, p + 4 all prime is 3, 5, 7 (one of any three consecutive odd numbers is divisible by 3).
A typical idea: test a prime by its remainder on division by 3 (or 2, 4, 6).
p and p² + 2 are both prime. Find p.