A prime number is a positive integer real number which has no integer divisors except 1 and the number itself.

Thus, 7 is prime because it is only divisible by 1 and 7.  17 is prime because it is only divisible by 1 and 17.  15, on the other hand, is not prime, as it is 3 x 5.

A composite number (that is, a number which is not prime), can be factorised. That is, it can be divided into number with which it is divisible. Thus, the factors of 15 are 3 and 5.

The number 24 can be divided in more than one way.  It is 2 x 12.  It is 4 x 6.  It is 3 x 8.  It is 2 x 2 x 2 x 3.

However, a composite number can only be divided into it's prime factors in one way.  4 and 6 are not prime factors of 24, because neither 4 nor 6 is itself prime.  24, divided into it's prime factors, is 2 x 2 x 2 x 3.  This can also be written as 2³ x 3¹.  This is the only way in which 24 can be factorised into its prime factors.  This prime factorisation of 24 is unique.

The number 1 is not now generally regarded as a prime.  If it was, then the uniqueness of prime factorisation would not apply.  In the above example, 24 could be factorised as 2³ x 3¹, or 1¹ x 2³ x 3¹, or 1² x 2³ x 3¹, or 1³ x 2³ x 3¹, and so on.

The total number of primes is infinite. There is no highest prime.

This fact has been known since the time of Euclid, and can quite easily be proved.

Let us imagine that there is a highest prime, which has the value p.  Now multiply all the primes up to and including p.  Let us call the result q.  q is thus the product of all the primes.

Now add 1 to q.  Now try to factorise q + 1.  It cannot be divisible by any of the primes up to and including p, because it is 1 more than a multiple of all these numbers.  Thus, q + 1 must either itself be prime, or it must be a multiple of primes greater than p, thus demonstrating that p was not really the largest prime after all!

2 x 3 x 5 + 1 = 31, which is prime.  2 x 3 x 5 x 7 + 1 = 211, which is also prime.  2 x 3 x 5 x 7 x 11 + 1 = 2311, which is prime.  However, 2 x 3 x 5 x 7 x 11 x 13 + 1 = 30031, which is not prime, as it is 59 x 509, both of which are primes higher than 13.

Many people have been fascinated and intrigued by the distribution of primes.  On a small scale at least, we find that wherever in the table of primes we look, the size of the gaps between adjacent primes appears quite random.  On a large scale however, primes become scarcer as we go higher (even though there is no highest prime).  On a large scale, the total number of primes up to and including any particular prime number p is comparatively close to

p ————— ln(p)

Fermat's Little Theorum

He wrote it in a way not all that easy for all to understand.

It has been variously stated in the following ways:

     if p is a prime, then the remainder on dividing  a^p – a  by  p  is zero for all values of a
     if p is a prime, and a < p, then the remainder on dividing  a^(p–1) – 1  by  p  is zero for all values of a

Fermat's Little Theorum can be used to prove a large number to be composite, even if one does not know any of the factors of the number.

Fermat Numbers

A Fermat Number is 1 + 2^a, where a is itself a power of 2.

     F0 = 1 + 2¹ = 1 + 2 = 3
     F1 = 1 + 2² = 1 + 4 = 5
     F2 = 1 + 2⁴ = 1 + 16 = 17
     F3 = 1 + 2⁸ = 1 + 256 = 257
     F4 = 1 + 2¹⁶ = 1 + 65536 = 65537

All of these are prime. Fermat conjectured that all Fermat Number were prime. However, Euler proved that

     F5 = 1 + 2³² = 1 + 4,294,967,296 = 4,294,967,297, is not prime.
     4,294,967,297 = 641 x 6,700,417.

Twin Primes

Since 2 is the only even prime, no primes other than 2 and 3 can be consecutive.

There are numerous examples of pairs of primes of which one of the numbers is just 2 above the other. These are often called Twin Primes. Examples are 3 and 5; 5 and 7; 11 and 13; 17 and 19. It is widely believed (though not proven), that there are an infinite number of twin primes.

Some examples of large primes

The second and third primes above 10¹² (a million million) are twin primes. So are the second and third primes below 10¹².

The three primes below 10¹², and the three above, are

     0,999,999,999,959
     0,999,999,999,961
     0,999,999,999,989

     1,000,000,000,039
     1,000,000,000,061
     1,000,000,000,063

Primes below and above 2⁶⁴ (which is 18,446,744,073,709,551,616), are

     18,446,744,073,709,550,719
     18,446,744,073,709,550,771
     18,446,744,073,709,550,773
     18,446,744,073,709,550,791
     18,446,744,073,709,550,873
     18,446,744,073,709,551,113
     18,446,744,073,709,551,163
     18,446,744,073,709,551,191
     18,446,744,073,709,551,253
     18,446,744,073,709,551,263
     18,446,744,073,709,551,293
     18,446,744,073,709,551,337
     18,446,744,073,709,551,359
     18,446,744,073,709,551,427
     18,446,744,073,709,551,437
     18,446,744,073,709,551,521
     18,446,744,073,709,551,533
     18,446,744,073,709,551,557

     18,446,744,073,709,551,629
     18,446,744,073,709,551,653
     18,446,744,073,709,551,667
     18,446,744,073,709,551,697
     18,446,744,073,709,551,709
     18,446,744,073,709,551,757
     18,446,744,073,709,551,923
     18,446,744,073,709,551,947
     18,446,744,073,709,552,009
     18,446,744,073,709,552,109
     18,446,744,073,709,552,157
     18,446,744,073,709,552,213
     18,446,744,073,709,552,253
     18,446,744,073,709,552,267
     18,446,744,073,709,552,333
     18,446,744,073,709,552,357
     18,446,744,073,709,552,361
     18,446,744,073,709,552,373
     18,446,744,073,709,552,421
     18,446,744,073,709,552,423
     18,446,744,073,709,552,501

So, as can be seen, the gaps between primes vary very greatly, and twin primes are still to be found, even at very-large numbers.