# Divisors and prime numbers

## Prime numbers

### Prime numbers and composite numbers

#### Definition

A prime number is a number which does not have any divisors other than $$1$$ and itself.

By convention we do not refer to $$0$$ or $$1$$ as prime numbers.

#### Identifying prime numbers

Divisors must be smaller than the number. As a result it is easy to identify early prime numbers, as we can try to divide by all preceding numbers.

#### Examples of prime numbers

$$[2, 3 5, 7, 11, 13,...]$$

#### Composite numbers

Composite numbers are numbers that are made up through the multiplication of other numbers.

They are not prime.

### Euler’s totient function

This functions counts numbers up to $$n$$ which are relatively prime

eg for 10 we have $$1$$, $$3$$, $$7$$, $$9$$.

So $$\phi (10)=4$$

## Other

### Frobenius number

Given a set of nautral numbers, the Frobenius number is the biggest number which can’t be made as linear combination of the set.