The Fundamental Theorem of Arithmetic

Theorem

Every integercan be represented as a product of prime factors in only one way, apart from the order of the factors.

Proof: We use induction onThe theorem is true forAssume then that it is true for all integersIfis prime then n satisfies the theorem. Suppose then that n is composite and has two factorisations, say

(1)

We need to show thatand that eachfor someSincedivides the productit must divide at least one factor. Relabelso thatdividesThensince bothandare primes. We may cancelon both sides of (1) to obtainIforthenThe induction hypothesis tells us that the two factorisations ofmust be identical apart from the order of the factors. Thereforeand the factorisations in (1) are identical.

In general each prime may occur more than once. We can factorise n into a product of powers of primes numbers and write

The fundamental theorem of arithmetic means that this form for the factorisation of n is also unique.

Once the prime power factorisation of two numbers is know then the greatest common divisor and lowest common multiple can easily be found.

Ifand then

1. the lowest common multiple, lcm, ofandis where

2. the highest common factor or greatest common divisor of n and m iswhere