The Fundamental Theorem of Arithmetic
Theorem
Every integer
can be represented as a product of prime factors in only one way, apart from the order of the factors.
Proof: We use induction on
The theorem is true for
Assume then that it is true for all integers
If
is prime then n satisfies the theorem. Suppose then that n is composite and has two factorisations, say
(1)
We need to show that
and that each
for some
Since
divides the product
it must divide at least one factor. Relabel
so that
divides
Then
since bothand
are primes. We may cancelon both sides of (1) to obtain
If
or
then
The induction hypothesis tells us that the two factorisations of
must be identical apart from the order of the factors. Therefore
and 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.
If
and 
then
1. the lowest common multiple, lcm, ofand
is 
where
2. the highest common factor or greatest common divisor of n and m iswhere 