Prime Numbers

A Prime number is a natural number with exactly two distinct natural number divisors: 1 and itself. Otherwise a number is called a composite number. Therefore, 1 is not a prime, since it only has one divisor, namely 1. A number $n > 1$ is prime if it cannot be written as a product of two factors $a$ and $b$, both of which are greater than 1: n = ab.

• The first twenty-six prime numbers are:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101

• Note: only positive numbers can be primes.

• There are infinitely many prime numbers.

• The only even prime number is 2, since any larger even number is divisible by 2. Also 2 is the smallest prime.

• All prime numbers except 2 and 5 end in 1, 3, 7 or 9, since numbers ending in 0, 2, 4, 6 or 8 are multiples of 2 and numbers ending in 0 or 5 are multiples of 5. Similarly, all prime numbers above 3 are of the form $6n-1$ or $6n+1$, because all other numbers are divisible by 2 or 3.

• Any nonzero natural number $n$ can be factored into primes, written as a product of primes or powers of primes. Moreover, this factorization is unique except for a possible reordering of the factors.

• Prime factorization: every positive integer greater than 1 can be written as a product of one or more prime integers in a way which is unique. For instance integer $n$ with three unique prime factors $a$, $b$, and $c$ can be expressed as $n=a^p*b^q*c^r$, where $p$, $q$, and $r$ are powers of $a$, $b$, and $c$, respectively and are $\geq1$.
Example: $4200=2^3*3*5^2*7$.

• Verifying the primality (checking whether the number is a prime) of a given number $n$ can be done by trial division, that is to say dividing $n$ by all integer numbers smaller than $\sqrt{n}$, thereby checking whether $n$ is a multiple of $m\leq{\sqrt{n}}$.
Example: Verifying the primality of $161$: $\sqrt{161}$ is little less than $13$, from integers from $2$ to $13$, $161$ is divisible by $7$, hence $161$ is not prime.
Note that, it is only necessary to try dividing by prime numbers up to $\sqrt{n}$, since if n has any divisors at all (besides 1 and n), then it must have a prime divisor.

• If $n$ is a positive integer greater than 1, then there is always a prime number $p$ with $n < p < 2n$.