Since n = 1.n = n.1, every number has itself and 1 as divisors. The numbers with two distinct divisors, i.e. with 1 and n as their only divisors, are called prime numbers. A number that is not 0, 1 or a prime is called a composite number.
A process to find all the primes up to any chosen bound b is the sieve of Eratosthenes, which proceeds by listing all the numbers from 2 to b, then to mark every 2nd number after 2, every 3rd number after 3, every 5th number after 5 (4 being already marked), every 7th number after 7 (6 already marked) and in general every nth number after the next unmarked number n.
List of all primes up to 1000 (base ten): 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, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197; 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293; 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397; 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499; 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599; 601, 607, 613, 617, 719, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691,; 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797; 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887; 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997.
Numbers that have only 2 and 3 as divisors I call basals. The table below shows all basal numbers less than 10000 in base ten. The numbers are arranged according to the following scheme: a down step multiplies by 2, a right step multiplies by 3. Other lines multiply by m, where m is the first number on the parallel line from 1; for example diagonal steps down and to the right multiply by 6.
| 1 | 3 | 9 | 27 | 81 | 243 | 729 | 2187 | 6561 |
| 2 | 6 | 18 | 54 | 162 | 486 | 1458 | 4374 | |
| 4 | 12 | 36 | 108 | 324 | 972 | 2916 | 8748 | |
| 8 | 24 | 72 | 216 | 648 | 1944 | 5832 | ||
| 16 | 48 | 144 | 432 | 1296 | 3888 | |||
| 32 | 96 | 288 | 864 | 2592 | 7776 | |||
| 64 | 192 | 576 | 1728 | 5184 | ||||
| 128 | 384 | 1152 | 3456 | |||||
| 256 | 768 | 2304 | 6912 | |||||
| 512 | 1536 | 4608 | ||||||
| 1024 | 3072 | 9216 | ||||||
| 2048 | 6144 | |||||||
| 4096 | ||||||||
| 8192 |
Any arithmetical progression a, q+a, 2.q+a, ... where a and q are relatively prime, can contain primes. It has been shown that it is not possible to get more consecutive primes than p−1 where p is the smallest prime non-divisor of q. [Lines]
All primes other than 2 are of the forms 4.n±1. In the sequences of primes of the forms 4.n − 1: 3, 7, 11, 19, 23, 31, 43, 47, 59, 67, 71, 79, 83, ... and 4.n + 1: 5, 13, 17, 29, 37, 41, 53, 61, 73, 89, 91, ... there can only be runs of two primes.
All prime numbers, apart from 2 and 3, are of the forms 6.n ± 1. I call all numbers of this form primals, thus 1 is a primal. The non-prime primals are numbers expressed as products of the larger primes, i.e. not divisible by 2 or 3. In the sequences of the forms 6.n + 1: 7, 13, 19, 31, 37, 43, 61, 67, 73, 79, 97, ... and 6.n &minus 1: 11, 17, 23, 29, 41, 47, 53, 59, 71, 83, 89, ... there are 'runs' of four primes.
This property accounts in part for why primes often occur in pairs differing by 2. I list here the pairs of primals, up to 144 ± 1, with compound numbers underlined: (5, 7), (11, 13), (17, 19), (23, 25), (29, 31), (35, 37), (41, 43), (47, 49), (53, 55), (59, 61), (65, 67), (71, 73), (77, 79), (83, 85), (89, 91), (95, 97), (101, 103), (107, 109), (113, 115), (119, 121), (125, 127), (131, 133), (137, 139), (143, 145).
Where are the primes most dense? Let P(n) be the number of primes less than or equal to n. Calculate P(n)/n. Answer from 2 to 8 the 'density' P(n)/n is 0.5 or more. After that it declines steadily.
The Goldbach conjecture (1742) that every even number is the sum of two primes has not been proved or disproved. (Chen 1974 established that if the even number is sufficiently large, it can be expressed as the sum of two primes or of a prime and a number with at most two prime factors. [Baker]) Vinogradov proved that every sufficiently large odd number is the sum of three primes.
Any composite number can be expressed as the sum of a series of two or more successive odd numbers unless it has only one even factor. [Reichmann]. If n = (2.k+1).d (d odd) then n = d + ... + d + ... + d, and working from the centre outwards we can get n = (d–2.k) + ... + (d–2) + d + (d+2) + ... + (d+2.k). Similarly if n = 2.k.e (e even) then n = e + ... + e + e + ... + e = (e+1–2.k) + ... + (e–1) + (e+1) + ... + (e–1+2.k). A number 2.odd (singly even) cannot be so expressed (but can be the sum of successive even numbers): 2.d = d+d = (d–1) + (d+1). The singly even numbers are: 2, 6, 10, 14, 18, 22, 26, 30, ... of the form 4.n+2 = 2.(2.n+1).
Numbers a, b are said to be relatively prime if they have no common factor. In other words aΛb = 1.
What is the first composite relatively prime to n? Answer: the square of the first prime not a factor of n.
What is the first number relatively prime to p^2 (p a prime)? Answer: the product of all primes less than p. This gives the sequence of prime products (Euclidean numbers?): 1, 2, 6, 30, 210, 2310, 30030, 510510, 9699690, ...
Theorem The product of any r consecutive numbers is divisible by r!. Since at least one of them has 2 as a divisor, at least one has 3 as a divisor, and so on.
Theorem (3.k)! has a factor 6^k. Since every three successive numbers have 2 and 3 as factors.
Euclid proved that, theoretically, there is always a prime higher than any given prime. His proof forms the numbers 2.3.5.7. ... .p + 1, i.e. one more than the product of all the primes up to and including a given prime p. This number gives a remainder of 1 on division by all primes up to and including p, so is either a new prime number or is divisible by a prime number greater than p. In practice, the numbers increase rapidly so we are liable to go beyond the limit of our register. Also actually locating the prime may present difficulties.
Numbers of this form are known as Euclidean numbers. For the first five values of p (2, 3, 5, 7, 11) the Euclidean numbers are primes (3, 7, 31, 211, 2311). The only other Euclidean primes with p up to 1031 occur when p is 31 and 379, 1019, 1021 (the last two generators are a prime pair). [Lines]
If P' denotes the first prime greater than 2.3.5.7. ... .p + 1 then a conjecture of Reo Fortune is that P' – 2.3.5. ... .p is always prime; no counter-example is known. [Lines]
For values of p up to 307 only six prime numbers of the form 2.3.5.7. ... .p)–1 are known. They occur for p = 3, 5, 11, 13, 41, 89. [Lines]
Euclid's proof can be put in a slightly different form: The proof depends on the fact that no two consecutive numbers can have the same divisor, because if x has divisor y then x+1 when divided by y will give a remainder of 1. If instead of x and x+1 we substitute x! and x!+1 then x!+1 cannot have any divisors common to x!. So if x!+1 has any prime divisors, they must be greater than x.
For values of n up to 230 the number n!+1 has been found to be prime when n = 1, 2, 3, 11, 27, 37, 41, 73, 77, 116, 154. For values of n up to 100 the number n!–1 is prime when n = 3, 4, 6, 7, 12, 14, 30, 32, 33, 38, 94. [Lines]
The next n−1 numbers which follow n!+1 are necessarily composite, since n!+k, with 1 ≤ k ≤ n, must be divisible by k. Thus we can find strings of composite numbers as long as we wish. The biggest gap between consecutive primes below 3.(10^12) is the 651 composites beginning 2614941710600. [Lines]