Prime numbers have mystified humans since the dawn of time. Much progress has been made on deciphering their unique properties and behaviours.

Prime Numbers

Prime numbers are positive integers that can only be divided by 1 and themselves. The first few prime numbers are 2,3,5,7,11,13,17,19 and 23. Non-prime numbers are called composite numbers, except for 1, which is neither prime nor composite, and is called the unit.

How many primes are there?

There are an infinite number of primes. There are several proofs of this fact, the first was by Euclid. Euclid asked us to suppose that there are only a finite number of primes, say p₁ to p_n. However the product of these primes plus 1 must be divisible by some prime, yet is not divisible by any of the primes listed, assumed to be a complete set, therefore the assumption that there are only a finite number of primes is wrong, and hence there are an infinite umber of primes.

Mersenne Primes

Mersenne primes are named after Marin Mersenne. They are prime numbers of the form 2^p-1. Note that p must be a prime, although this does not guarantee that 2^p-1 is prime. The first few Mersenne primes are 2²-1=3, 2³-1=7, 2⁵-1=31, 2⁷-1=127. However 2¹¹-1=2047=23*89.

There are 39 Mersenne primes currently known, and the largest Mersenne prime is the largest known prime. An open question is whether an infinite number of Mersenne primes exist.

Factorization

If n is an integer greater than 1, then the factorization of n consists of the primes p₁ ... p_n such that the products of all the p_i's is n. Usual notation is to group similar primes together, and write n=p₁^e₁...p_k^e_k. This is called the factorization of n, the e_i's are called exponents.

For example 36 is written 2².3². This representation is unique because of the Unique Factorization Theorem.

Unique Factorization Theorem

Also known as the Fundamental Theorem of Arithmetic, this theorem states that any n has exactly 1 factorization. For example, 12=2².3, but does not have any other factorization.

Proof: Let n=p₁...p_j=q₁...q_k with j>=k. Cancel all terms such that p_a=q_b for some a and b. If some primes remain, there is a contradiction in that some p_a both divides and does not divide n at the same time.

Fundamental Theorem of Arithmetic

See Unique Factorization Theorem.

Prime Number Theorem

Let pi(x) denote the number of primes up to x. Then pi(x) is asymptotic to x/log(x), that is, the ratio of these two functions tends to 1.

A more accurate approximation to pi(x) is given by Li(x), the logarithmic integral. The difference between these two functions is controlled by the real part of the zeroes of the Riemann zeta function.

Anti-divisor

A concept which extends the sieve of Erastoneues by viewing the striking out process as a waveform. The primes factors of a number are determined by the zeroes of this waveform, and anti-divisors are given by the numbers under or above the peak and troughs of waves.

For example, the anti-divisors of 8 are 3 and 5.

Anti-divisors were used by Perry to prove the Twin Prime Conjecture.

For further information, see Anti-divisor.