# 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.

### 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

### Pseudoprimes

## 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.