Divisors and prime numbers

Prime numbers

Prime numbers and composite numbers


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.

Relatively prime numbers

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\)

Euler’s theorem

Fermat’s little theorem



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.