31.07 - Integer and prime factorisation

Integer factorisation (decomposition)

Integer factorisation is the decomposition of a product into its factors.

Every integer bigger than 1 which has two or more factors that are bigger than 1 are called composite numbers. Every other number is called a prime number.

For example: The factors of $12$ are:

• $2\times 6$
• $3\times 4$
• 12 is a composite number The factors of $17$ are:
• none
• 17 is a prime number

Prime factorisation (decomposition)

Prime decomposition is like integer factorisation, but you keep factoring until all integers are prime numbers. To calculate the prime decomposition of any integer, you start by dividing it by the smallest prime number (2) until the result is not an integer.

Note down the amount of divisions you did with that number and move to the next lowest prime number(3, 5, 7…) until you reach 1

For example, the number 864:

• 846 can be divided by 2 5 times before reaching 27.
• 27 can be divided by 3 3 times before reaching 1.
• The prime decomposition of 864 is $2\times 2\times 2\times 2\times 2\times 3\times 3\times 3$ or $2^5\times 3^3$

next article

The next article will go over the greatest common divisor and least common multiple