Primes and Divisibility

Prime numbers are the most interesting objects in number theory. The mystery of prime numbers lies in the fact that there is no known algorithm whose $n$ -th step gives the $n$ -th prime number. Primes are like surprise in your life: there is no simple rule to know how they follow each other in the sequence of natural numbers, they just show up out of the blue. And you won’t ever run out of surprises as Euclid, the Greek wizard of math proved that there are infinitely many primes.

His argument is ingenious: first, he observed that every positive integer which is greater than $1$ has a prime divisor. Indeed, either it is itself a prime, or otherwise it is the product of two smaller natural numbers. If any of these is a prime then we are done. However, if none of these two smaller numbers is a prime then we repeat our argument for any of them and continue this process. As our numbers in the process are strictly decreasing after some steps the procedure terminates and we arrive at a prime divisor of our original number. Now Euclid argued as follows: assume that there are only finitely many prime numbers. Then we construct a number which has no prime divisor. In fact, if we take the product of all prime numbers — don’t forget! There are only finitely many, by assumption! — then this number is divisible by all prime numbers. Hence, adding $1$ to this number the resulting number has the remainder $1$ after dividing with any prime, thus it has no prime divisor. You can see that both arguments of Euclid are correct, but the second one starts with the assumption that there are only finitely many primes. So, this assumption is false.

Prime numbers are often used in cryptography or security for technology and the internet — probably, because of their unpredictable behaviour. For us, math fans they are the sources of fun and joy, mystery and magic. Although there is no exact formula which describes their sequence but the statistical behaviour of primes in the large, can be modeled. Namely, the Prime Number Theorem states, roughly speaking, that the probability that a given, randomly chosen number is prime is inversely proportional to its number of digits.

There are famous unanswered questions about primes. One of them is Goldbach’s Conjecture, that every even integer greater than $2$ is the sum of two primes, or the Twin Prime Conjecture, that there are infinitely many pairs of primes whose difference is $2$ . It is really amazing that there are so many questions about primes which are very easy to understand, even for juniors, and still there is no answer.

In the world of natural numbers prime numbers play the role of a kind of building blocks. Indeed, the Fundamental Theorem of Arithmetic states that every integer larger than $1$ can be written as a product of primes. This is the so-called prime factorization. In addition, this factorization is unique: every natural number greater than 1 uniquely determines those primes which occur in its factorization, and also the power on which a given prime occurs is unique. For instance, the number $36$ has the unique factorization as $36=22\cdot 32$ . This means, the number $36$ is uniquely characterized by the two pairs: $(2,2)$ and $(3,2)$ . Here the first components of the pairs indicate which primes belong to $36$ and the second components means the number how many times that prime occurs.

A little bit more advanced observation is that in this way every natural number can be considered as a function on the set of all prime numbers which assigns to each prime the number of occurrences of this prime in the factorization of our number. If the prime does not occur then the function takes the $0$ value at this prime. These functions have the property that their values are non-negative integers and they are zero outside a finite set: clearly, each natural number greater than $1$ has only finitely many primes occurring in its factorization. On the other hand, every function on the set of all primes with these two properties corresponds to a unique natural number: to get it we simply take each prime where the function is nonzero as many times as the function value is at this prime, and form their product of these numbers. Thus we set up a one-to-one correspondence between the set of all natural numbers greater than $1$ and the set of all functions on the primes with the given two properties. In fact, we may include the number $1$ too, if we assign the identically zero function to it: all primes occur with zero exponent in its “factorization”. So, prime factorization of a given natural number is nothing but finding the corresponding function. This can be a hard job — normally, we make it by trial division. This routine means that given the number we try to divide it by all consecutive primes which are less than the number. Starting with $2$ we try to divide. If succeeded, then try to divide again, and again until we fail — then we have the number of occurrences of this prime. Of course, if we fail then we take the next prime and repeat the process. The Fundamental Theorem of Arithmetic guarantees that our job will terminate after finitely many steps. In fact, we don’t need to check all primes which are less than our number. Indeed, as every divisor has a pair, which is the quotient after division, hence it is enough to check those primes which are not greater than the square root of our number — one of the two members of the pair can’t be greater than that square root.

For instance, suppose that we have to find the prime factorization of $999991$ . Of course, we can start with dividing by the consecutive primes but the given number is really very large, even its square root is about $1000$ . Is there a quicker way? Well, let’s first try to find two whole numbers greater than $1$ whose product is $999991$ . We observe that $999991=1000000-9$ , the difference of two squares, $1000^2-3^2$ . Using the identity $(a+b)(a-b)=a^2-b^2$ we have $999991=1003 \cdot 997$ . Now it is enough to factorize $1003$ and $997$ . Both the square roots of $1003$ and $997$ are between $31$ and $32$ hence it is enough to try to divide with the primes from $2$ to $31$ in both cases. We have nice division tests for $2, 3, 5$ and $11$ (do you remember?) which fail for both numbers, and none of them is divisible by $7$ . Why? You can check it directly, but if $1003$ is divisible by $7$ , then so is $1010=1003+7$ , hence so is $101=70+28+3$ , which is not the case. Similarly, if $997$ is divisible by $7$ , then so is $990=997-7$ , but $990$ is the product of $2, 5, 9$ and $11$ , none of them divisible by $7$ . We can check in the similar way, very quickly that our two numbers are not divisible by $13$ , either. But we hit pay-dirt at $17$ : namely, $1003$ is the product of $17$ and $59$ , two primes. Some more primes left to check in the case of $997$ : these are $19, 23, 29$ and $31$ . We can speed up the check-up in these cases by some tricks, like if $997$ is divisible by $23$ , then so is $1020=997+23$ , and then so is $102= 2\cdot 51=2\cdot 3\cdot 17$ , which is not the case. Finally, we arrive at the conclusion that the prime factorization of $999991$ is $17\cdot 59\cdot 997$ .

It is reasonable to ask the following question: is it true that if two natural numbers are close to each other, then their prime factorizations are “similar”? Of course, there is no such similarity — otherwise the arrival of a new prime didn’t surprise us. For instance, $24000000$ has the prime factorization $2^9\cdot 3^1\cdot 5^6$ , so, it has a great number of factors, but the next number, $24000001$ is prime. It seems reasonable to try to get some information about the gaps between two consecutive primes. We know that the gap is at least two, as one of two consecutive natural numbers is always even, hence — except the only case of $2$ and $3$ — two successive natural numbers cannot be both primes. The Twin Prime Conjecture is looking for the answer if this gap can be so small infinitely many times, or twin primes do not exist in the empire of huge numbers. And we can look for longer gaps, of course. How long these gaps can be? It is an amazing observation that the gap between two consecutive primes can be arbitrary long. This means that, listing the natural numbers successively, we never know when the surprise comes — it may happen that our life is not enough to arrive at the next prime. That’s why it is a surprise, by the way. To prove this tricky property of primes we argue as follows: let $n$ be a number and let $N$ be the product of all primes which are smaller than $n+2$ . Then none of the $n$ successive numbers $N+2, N+3, N+4,\dots, N+n, N+(n+1)$ is prime. Why? Well, if we take any of the numbers from $2$ to $n+1$ , say $k$ , it has a prime factor, which is clearly smaller than $n+2$ . Further, this prime divides $N$ , hence it divides $N+k$ , too. Thus no number in the given list is prime. This is some bad news for gold miners: although I found a precious piece of gold, maybe I’ll find the next one after a very long time, only. If I survive. But still there is good news, too: the gap to the next prime cannot be larger than the number we start our search at. This was a famous desire of a desperate “gold miner”: Joseph Bertrand, who could verify his wish empirically for numbers not greater than $3$ million. In 1850 Pafnuty Chebyshev calmed down Bertrand proving his dream in full generality: for every natural number greater than $1$ there is some prime number between the number and its double. The proof is not easy, later it has been simplified by the Indian genius Ramanujan, but it is still too sophisticated to be included here. Another proof was given by the Hungarian Pál Erdős, one of the most prolific and extraordinary mathematicians in the 20th century. He proved the result in his first published paper, which appeared in 1932, when Erdős was 19.

So, if we arrive at the prime $p$ , then the next one will be less than $2p$ . Although the gaps between consecutive primes can be arbitrarily large, but this can only happen in the Huge Number’s World. How large are the largest known prime numbers? Nowadays the hunt continues and high-tech is involved in finding larger and larger prime numbers. In fact, this is a kind of IQ-test for the fastest computers if they are able to find an even larger prime. And, of course, it is a test for those math guys who provide the algorithms, and for those technicians who construct the hardware.

As of January, 2016, the largest known prime number has $22338618$ decimal digits. Twenty two million digits… How many blank A4 sheets do we need to write down this number? And what is the use of this championship, finding very large prime numbers using computers? Well, this is the nature of the human being: Citius — Altius — Fortius, as the Olympic motto says. Faster, Higher, Stronger.

Vélemény, hozzászólás? Válasz megszakítása

Hozzászólás küldéséhez be kell jelentkezni.