# Composite and prime numbers

A prime number is any number that has no factors. In other words, the only numbers that it can be divided by exactly are 1 and itself. Any other numbers are 'non-prime' or composite.

Exercise: which of the following are prime?:

3, 4, 5, 6, 9, 11, 12, 20, 21, 22, 23

Theorem: Any non-prime number can be expressed as the product of prime numbers.

For example, consider 408. This can be broken down into factors as follows:

 408 408 = 2 × 204 408 = 2 × 2 × 102 408 = 2 × 2 × 2 × 51 408 = 2 × 2 × 2 × 3 × 17

The theorem seems obvious, but is actually somewhat trick to prove. [The proof is 'by contradition' and starts out by supposing there is at least one number for which this is not true, i.e. it is not prime, but cannot be written as a product of prime factors. If there are several such numbers, choose the smallest of them. It cannot be written as the product of primes, but has a factor (otherwise it would be prime). Any of its factors must be smaller than it, and is either prime or can be written as the product of primes. But we started with the smallest such number. This leads to a contradiction.]

For large numbers, the above writing of the number of a product of primes can get rather long. It is then convenient to abbreviate it. For example, 408 = 23 × 3 × 17. The superscript is called an exponent or 'power'. Thus 'two to the power four' (24) = 2 × 2 × 2 × 2 = 16.

Any large number can be written in this way. For example: 455400 = 23 × 32 × 52 × 11 × 23

## Checking to see is a number is prime

You only need to see if prime numbers smaller than it 'go into' it exactly. Actually, you don 't need to check all the prime numbers smaller than it. For example, if you are checking 149, you note 2 cannot be a factor (as it is an odd number), 3 cannot be a factor (as the sum of the digits is 14, i.e. not divisible by 3), 5 cannot be a factor (as it doesn't end in '0' or '5)'. Trying 7, we calculate 149/7 = 21 remainder 2 and therefore 7 is not a factor. The next prime is 11; 12 × 11 = 132, and 13 × 11 = 143; so 149/11 = 13 remainder 6.

The next prime after 11 is 13, but you don't need to check it. If 13 was a factor of 149, there would be a number that multiplied by 13 to make 149. That number would have to be less than 13 (as 13 × 13 = 169). But we have already needed checked all the primes smaller than 13. S, to check to see if a number is prime you only need to check the primes less than the square root of that number.

For example, to check 397, we only need to check primes less than 20 (as 20 × 20 = 400). To check 997, you need to check all the primes up to 31 (32 is the next number, it is not prime, and 32 × 32 = 1024).