All positive integers except the number one can be classified as either composite numbers or primes. A positive number is composite if it can be expressed as the product of two or more positive integers, which are its factors. In some cases some of these factors may be equal. Foe example 4 and 6 are composite , 4 = 2 x 2 and 6 = 2 x 3.
A positive integer is called a prime if it is different from 1 and not composite. In other words it can not be expressed as the product of two positive integers apart from the trivial case of itself and one. Examples include 2, 3, 5 and 7.
A composite number can be decomposed into a product of prime numbers. Each factor which is composite can be decomposed into smaller factors and ultimately the factors will all be prime. For example, 60 = 5 x 12 = 5 x 4 x 3 = 5 x 2 x 2 x 3.
Two integers are called relatively prime or prime to each other if they contain no common prime factors.
The decoposition of numbers into their prime factors can be used to find the highest common factor or the least common multiple of the given numbers.
Taking 9 and 12 as examples. They can be decomposed into their respective prime factors as follows:
9 = 3 x 3 12 = 2 x 2 x 3
To get their highest common factor simply find the product of the prime factors they have in common. In this case the two numbers have 3 in common. As it is the only prime factor they share their highest common factor is 3.
To get their least common multiple you get the product of the highest occurance of each prime number. In the list of prime factors for 9 and 12 we find that 3 occurs twice for 9 and once for 12, so we take two 3s. We get two 2 twice for 12 but no occurance for 9 so we take two 2s. Our highest common multiple is therefore
3 x 3 x 2 x 2 = 36