| Currently there may be errors shown on top of a page, because of a missing Wiki update (PHP version and extension DPL3). |
| Topics | Help • Register • News • History • How to • Sequences statistics • Template prototypes |
Prime
A prime number (or only prime) is an integer greater than 1 that is only divisible by itself and 1. The first few prime numbers are 2, 3, 5, 7, 11, 13, 17, 19.
It has been known since the time of Euclid (365 BC - 265 BC) that there are infinitely many primes. Suppose, he said, that there are a finite number of them. Then one of them, call it P, will be the largest. Now consider the number Q, larger than P, that is equal to the product of the consecutive whole numbers from 2 to P plus the number 1. In other words, Q = (2 x 3 x 4 x 5 ... x P) + 1. From the form of the number Q, it is obvious that no integer from 2 to P divides evenly into Q, because each division would leave a remainder of 1. If Q is not prime, it must be evenly divisible by some prime larger than P. On the other hand, if Q is prime, Q is itself a prime larger than P. Either possibility implies the existence of a prime larger than the assumed largest prime P. This means that the idea of a 'largest prime' is fiction. And, if there is no largest prime the primes must be infinite.
All prime numbers greater than 3 are of the form 6q + 1, or 6q + 5. The number 17, for example, is (6 • 2) + 5. While 19 = (6 • 3) + 1. This result can be proved quite simply by the following:
- Let p, q, r be positive integers
- Let p be of the form 6q + r
- the remainder r can be only 0, 1, 2, 3, 4, or 5
- If r = 0, 2, or 4, then p is divisible by 2 and so p is not prime
- If r = 3, then p is divisible by 3 and so p is not prime
- So, if p is prime >3, r will be either 1, or 5
- If p = 7, p = 6q + 1 and if p = 11, p = 6q + 5
- So if p = prime >3 then r = 1 and r = 5 are both necessary and sufficient
However, being 1 more or 5 more than a multiple of 6 is not enough to make a number prime. The number 35 is 5 more than a multiple of 6, but is not prime, and the number 25 is 1 more than a multiple of 6 but is not prime.
Multiples of 6 all end with either a 0, 2, 4, 6, or 8. Which means that prime numbers must end with either 1 more or 5 more than these digits. Therefore, all primes greater than 2 will end with a 1, 3, 5, 7, or 9, and, since any number ending in 5 is divisible by 5, only one of them will end with a 5. So we know what they look like, and we know what they are made of, but not all numbers that look like them or are made like them are prime.
