Factorising a number into its prime factors means identifying its elementary “bricks”. The Fundamental Theorem of Arithmetic guarantees that this factorisation is unique: from it one reads off the GCD, the LCM, the number of divisors and divisibility. The section includes the sieve of Eratosthenes algorithm for listing the primes, the quick divisibility rules and the ideas that prove them.
- Prime factors
- Factorising a number into primes
- GCD and LCM
- The fundamental theorem of arithmetic
- Why the FTA is fundamental
- Consequences of the FTA
- The sieve of Eratosthenes
- Why it is enough to stop at the square root of N
- How many prime numbers are there
- Divisibility rules
- Checking the divisibility rules
- The idea behind the proof of the rules