Prime Numbers

Some facts about them

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 23 x 31.  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 23 x 31, or 11 x 23 x 31, or 12 x 23 x 31, or 13 x 23 x 31, 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 qq 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  ap – 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 + 2a, where a is itself a power of 2.

F0 = 1 + 21 = 1 + 2 = 3
F1 = 1 + 22 = 1 + 4 = 5
F2 = 1 + 24 = 1 + 16 = 17
F3 = 1 + 28 = 1 + 256 = 257
F4 = 1 + 216 = 1 + 65536 = 65537

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

F5 = 1 + 232 = 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 1012 (a million million) are twin primes. So are the second and third primes below 1012.

The three primes below 1012, 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 264 (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.

Last updated 9 April 2019