Primes and the fundamental theorem of arithmetic
Master primes and the fundamental theorem of arithmetic in Year 11 VCE Specialist Mathematics. A prime has exactly two positive divisors, and the fundamental theorem of arithmetic guarantees every integer greater than \(1\) has a unique prime factorisation. It sits in the Algebra, number and structure area of study of the VCE Mathematics Study Design (VCAA), within the Proof and number topic of Unit 1.
You will learn to test primality by trial division up to \(\sqrt{n}\), write numbers in prime-power form, read the HCF, LCM and the number of divisors straight from the factorisation, and follow Euclid's proof that the primes never run out — number-theory tools that support the proof work of Unit 1.
Theory
A prime number has exactly two positive divisors: \(1\) and itself. The fundamental theorem of arithmetic says every integer greater than \(1\) is a prime or can be written as a product of primes in exactly one way (up to order). In Year 11 Specialist Mathematics this unique prime factorisation is the tool behind primality testing, the HCF and LCM, counting divisors, and Euclid's proof that the primes never run out.
A whole number \(n>1\) is prime if its only positive divisors are \(1\) and \(n\); otherwise it is composite. The number \(1\) is neither prime nor composite — it has just one divisor. The primes begin \(2,3,5,7,11,13,\dots\), and \(2\) is the only even prime.
To test whether \(n\) is prime by trial division, you need only try prime divisors up to \(\sqrt{n}\). If \(n\) had a factor larger than \(\sqrt{n}\), the matching co-factor would be smaller than \(\sqrt{n}\) and would already have been found — so no divisor up to \(\sqrt{n}\) means \(n\) is prime.
The fundamental theorem of arithmetic guarantees that every integer \(n>1\) factorises into primes in exactly one way apart from the order of the factors. Collecting repeats gives the prime-power form \(n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}\), for example \(360=2^3\times 3^2\times 5\). A factor tree is a convenient way to reach it.
Because the factorisation is unique, it controls the multiplicative structure of \(n\): the highest common factor (HCF) and lowest common multiple (LCM) of two numbers, and the number of positive divisors, can all be read straight off the prime powers.
Finally, Euclid used unique factorisation to prove there are infinitely many primes: no finite list can contain them all.
Every integer \(n>1\) has a unique prime-power factorisation:
From the factorisations of two numbers, take the lowest power of each shared prime for the HCF, and the highest power of every prime that appears for the LCM:
The number of positive divisors \(d(n)\) multiplies each exponent increased by one:
Because \(\min(a,b)+\max(a,b)=a+b\), the HCF and LCM satisfy the identity:
Finding and using a prime factorisation
- Factorise into primes. Repeatedly split off a prime factor (a factor tree helps) until every branch ends at a prime, then collect repeats into prime-power form \(n=p_1^{a_1}\cdots p_k^{a_k}\).
- Test primality by trial division only by primes up to \(\sqrt{n}\); no divisor there means \(n\) is prime.
- HCF: line up the factorisations and take each shared prime to its lowest power. No shared prime means the numbers are coprime and the HCF is \(1\).
- LCM: take every prime that appears, each to its highest power.
- Count divisors with \(d(n)=(a_1+1)(a_2+1)\cdots(a_k+1)\).
For example, \(48=2^4\times 3\) and \(180=2^2\times 3^2\times 5\) give \(\gcd=2^2\times 3=12\) and \(\operatorname{lcm}=2^4\times 3^2\times 5=720\).
Test each number for a factor other than \(1\) and itself:
| \(51\) | \(=\) | \(3 \times 17\) |
| \(57\) | \(=\) | \(3 \times 19\) |
| \(91\) | \(=\) | \(7 \times 13\) |
For \(53\), trial-divide only by primes up to \(\sqrt{53}\approx 7.3\):
| \(\text{try } 2,3,5,7\) | \(:\) | \(\text{none divides } 53\) |
| \(\Rightarrow\) | \(53 \text{ has no factor other than } 1,53\) |
\(53\) is prime; \(51,57\) and \(91\) are each a product of two smaller primes.
Split \(360\) into factors, then split each factor until only primes remain:
| \(360\) | \(=\) | \(36 \times 10\) |
| \(=\) | \((6\times 6)\times(2\times 5)\) | |
| \(=\) | \((2\times 3)(2\times 3)(2\times 5)\) |
Collect equal primes into powers:
| \(360\) | \(=\) | \(2\times 2\times 2\times 3\times 3\times 5\) |
| \(=\) | \(2^3\times 3^2\times 5\) |
\(360 = 2^{3}\times 3^{2}\times 5\).
Factorise each number into primes:
| \(90\) | \(=\) | \(2\times 3^2\times 5\) |
| \(84\) | \(=\) | \(2^2\times 3\times 7\) |
HCF: take each shared prime to its lowest power:
| \(\gcd(90,84)\) | \(=\) | \(2^1\times 3^1\) |
| \(=\) | \(6\) |
LCM: take every prime to its highest power:
| \(\operatorname{lcm}(90,84)\) | \(=\) | \(2^2\times 3^2\times 5\times 7\) |
| \(=\) | \(1260\) |
Check the product identity:
| \(\gcd\times\operatorname{lcm}\) | \(=\) | \(6\times 1260 = 7560\) |
| \(90\times 84\) | \(=\) | \(7560\ \checkmark\) |
\(\gcd(90,84)=6\), \(\operatorname{lcm}(90,84)=1260\), and their product equals \(90\times 84=7560\).
Factorise \(200\), then apply \(d(n)=(a_1+1)(a_2+1)\cdots\):
| \(200\) | \(=\) | \(2^3\times 5^2\) |
| \(d(200)\) | \(=\) | \((3+1)(2+1)\) |
| \(=\) | \(4\times 3 = 12\) |
A number is a perfect square exactly when every exponent is even. For \(N=2^4\times 3^2\times 5\):
| \(\text{exponents}\) | \(:\) | \(4,\ 2,\ 1\) |
| \(\Rightarrow\) | \(\text{the exponent of } 5 \text{ is odd}\) |
\(200\) has \(12\) positive divisors; \(N\) is not a perfect square, because the exponent of \(5\) is odd.
Multiply the listed primes and add \(1\):
| \(N\) | \(=\) | \(2\times 3\times 5\times 7\times 11 + 1\) |
| \(=\) | \(2310 + 1\) | |
| \(=\) | \(2311\) |
Divide \(N\) by any listed prime \(p\): the product \(2310\) is divisible by \(p\), so:
| \(N \div p\) | \(=\) | \((\text{whole number}) + \tfrac{1}{p}\) |
| \(\Rightarrow\) | \(N \text{ leaves remainder } 1 \text{ by every listed prime}\) |
So \(N\)'s prime factorisation uses a prime not in the list. (In fact \(2311\) is itself prime.)
| \(\Rightarrow\) | \(\text{the list was incomplete}\) |
Any finite list of primes can be extended, so there are infinitely many primes.
Common pitfalls
Frequently asked questions
What is the fundamental theorem of arithmetic?
It states that every integer greater than \(1\) is either prime or can be written as a product of primes, and that this prime factorisation is unique apart from the order of the factors. For example, \(360=2^3\times 3^2\times 5\) and no other set of primes gives \(360\).
Why is \(1\) not a prime number?
A prime must have exactly two distinct positive divisors. The number \(1\) has only one divisor (itself), so it is neither prime nor composite. Excluding \(1\) is also what keeps prime factorisation unique — otherwise you could insert any number of \(1\)s.
How far do I need to test for factors to check if a number is prime?
Only up to \(\sqrt{n}\). If \(n\) had a factor bigger than \(\sqrt{n}\), its co-factor would be smaller than \(\sqrt{n}\) and you would have found it already. So if no prime up to \(\sqrt{n}\) divides \(n\), then \(n\) is prime.
How do I find the HCF and LCM from prime factorisations?
Factorise both numbers. For the HCF, take each shared prime to its lowest power; for the LCM, take every prime that appears to its highest power. For \(90=2\times 3^2\times 5\) and \(84=2^2\times 3\times 7\), the HCF is \(2\times 3=6\) and the LCM is \(2^2\times 3^2\times 5\times 7=1260\).
How do I count the number of divisors of a number?
Write it in prime-power form \(n=p_1^{a_1}\cdots p_k^{a_k}\) and multiply each exponent-plus-one: \(d(n)=(a_1+1)\cdots(a_k+1)\). For \(200=2^3\times 5^2\) this gives \((3+1)(2+1)=12\) divisors.
How did Euclid prove there are infinitely many primes?
Assume there were only finitely many primes \(p_1,\dots,p_k\). The number \(N=p_1p_2\cdots p_k+1\) leaves remainder \(1\) when divided by each \(p_i\), so it must have a prime factor not on the list. That contradicts the list being complete, so the primes cannot be finite in number.