HEJ, HU ISSN 1418-7108 Manuscript no.: ANM-000926-A

Important properties of prime numbers

Results in the ancient time
THEOREM 3. The number of primes is infinite. PROOF. (By EUCLID) Let us assume, that there are only finite prime numbers, $p_1, p_2, \dots, p_n$. Let us consider the number $N= p_1 \cdot p_2 \cdot \dots \cdot p_n + 1$. This number is not divisible by the primes listed above, and the number $N$ is not listed as a prime number, so it cannot be written in the form of Theorem 2. But this is not possible, thus $N$ is a new prime itself, or the product of new primes not listed.

 
  > ifactor(2*3*5*7*11*13*17+1);

$$(\,{\rm }19)\,(\,{\rm }97)\,(\,{\rm }277)$$

PROPOSITION 1. If a number $n$ has a prime divisor $p < n$, then it has a prime divisor $p_1 \le [\sqrt{n}]$.
Using this result, we are able to specify the prime numbers until $n$, if we know the primes until $[\sqrt{n}]$. The following method is called the sieve of ERATOSTHENES after the author. Let us write the positive integer numbers beginning with 2 (or 1). Let us consider the first number in the list (we erase and skip the number 1), and erase its multiples. After it we take the following non-erased number in the list, and repeat the procedure. If we reach a non-erased number greater than $\sqrt{n}$, then the sieving is complete.
After these results there was only very limited development in the prime number theory until the $17$th century, FERMAT's time. In the following the most important results of the past four centuries will be summarized.
The number of primes Let us denote the number of prime elements less-equal to $x$ by $\pi(x)$, where $x$ is a positive real number. From the result of EUCLID follows, that $\pi(x) \rightarrow \infty$, if $x \rightarrow \infty$. Already EULER noted, that $\lim_{x \rightarrow \infty} \frac{\pi(x)}{x} = 0$. This was first proved by LEGENDRE. The following very important theorem was conjectured in the late 1790s by LEGENDRE and GAUSS, and first proved by HADAMARD and DE LA VALLÉE POUSSIN (1896) with extremely complicated mathematical tools. Elementary proof was given first by PAUL ERDOS and A. SEELBERG (1948).
THEOREM 4. The big prime number theorem

$$\pi(x) \sim \frac{x}{\ln{x}}.$$

REMARKS 1. The notation $\sim$ means "asymptotic equal" i.e.

$$\lim_{x \rightarrow \infty} \frac{\pi(x)}{\frac{x}{\ln{x}}}=1.$$

2. Let us denote the $n$th prime number by $p_n$. From the result of the theorem follows $p_n \sim n \ln n$. 3. The approach presented in Theorem 4. can be improved with

$$\pi(x) \sim \int_2^x \frac{d u}{\ln{u}}.$$

To illustrate the results of the theorem with Maple, we write the function $\pi(x)$, and delineate it with $\frac{x}{\ln{x}}$ in a logarithmic coordinate-system.

  > a[2]:=0:
  > for i from 3 to 10000 do  a[i]:=a[i-1]:
  >   if isprime(i-1) then a[i]:=a[i]+1 fi:
  > od:
  > pi:=x->if x=trunc(x) then a[x] else a[trunc(x+1)] fi:

  > with(plots):
  > loglogplot(\{x/ln(x),pi(x)\},x=1.2..500,y=1..200);

By studying the figure we can see the stepfunction-like behaviour of $\pi(x)$ (plotted above), and the fact, that for larger numbers both of the functions fit tight the same asymptotic line. However, between two asymptotic equal functions it is allowed to be very large differences.

  > pi(10000); evalf(10000/ln(10000));

$$1229$$

$$1085.736205$$

  > ""/";

$$1.131950831$$

To point 2. of the Theorem, we can produce the $i$th prime number with the function ithprime.

  > ithprime(1000), evalf(1000*ln(1000));

$$7919, \,6907.755279$$

THEOREM 5. (First proved by EULER) The sum of the reciprocal value of prime numbers is infinite, i.e. $\sum \frac{1}{p} = \infty$.
REMARKS 1. Comparing with the sum of the reciprocal value of square numbers we get

$$\frac{\pi^2}{6} = \sum \frac{1}{n^2} < \sum \frac{1}{p} = \infty,$$

so the prime numbers are situated more densely. 2. It is true moreover, that

$$\sum_{p \le n} \frac{1}{p} \sim \ln \ln{n}.$$

Similarly as above, we write the functions $\sum \frac{1}{n^2}$ and $\sum \frac{1}{p}$ to test their behaviour.

  > sumsquare:=x->sum(1/n^2,n=1..x);

$${\it sumsquare} := x\rightarrow \sum _{n=1}^{x} \frac {1}{n^2}$$

  > sumprime:=x->sum(1/ithprime(p),p=1..x);

$${\it sumprime} := x\rightarrow \sum _{p=1}^{x} \frac {1}{{\rm ithprime}(p)}$$

  > evalf(sumsquare(1000)), evalf(sumprime(1000));

$$1.643934568, \,2.457411277$$

The function $\ln \ln x$ grows very slowly.

  > evalf(ln(ln(1000))),evalf(ln(ln(1000000)));

$$1.932644734, \,2.625791915$$

The distance of primes Analysing the result of Theorem 4., we conclude that the primes gradually become rarer and rarer (on the average). Their distribution is nevertheless irregular. For example it is obvious, that the sequence $(n+1)! + 2, (n+1)! + 3, \dots , (n+1)! + n+1$ contains no primes, at the same time we know very large consecutive primes. Let us denote the difference of the $n$th and $(n-1)$th prime number by $d_n$, i.e. $d_n = p_n - p_{n-1}$. There are very important results for large and small prime differences. From Theorem 4. follows that given an arbitrary small number $\varepsilon$ there are infinitely many numbers $n$ for which a) $d_n > (1 - \varepsilon) \ln n$, b) $d_n < (1 + \varepsilon) \ln n$. One of the important results for large prime differences was stated by BERTRAND and proved by CSEBISEV, namely if $n$ is a positive integer, then there is always (at least one) prime number between $n$ and $2n$. We know moreover, that there exists a constant number $c$, that for every suitable large number $n$ satisfies $d_n < n^c$, e.g. $c=38/61$ can be written. It is an open question, however, that between two consecutive square numbers falls in every case a prime number. If $d_n = 2$, than we call the numbers $p_n$ and $p_{n-1}$ twin primes. It is a very old conjecture, that there are infinitely many twin primes. Let us denote the number of twin primes less equal than $x$ by $N(x)$. The most important result here is, that there exists a positive constant $c$, for which $N(x)< c \frac{x}{\ln^2 x}$. Considering the prime number theorem this means that $N(x)$ is small compared with $\pi(x)$. To collect observations with Maple about the prime distances we can write programs with the tools reviewed above. Here a simple example will be presented, searching twin primes in a given interval.

  > twinprimes:=proc(a,limit)
  > local i,prev,act;
  >   prev:=isprime(a);
  >   for i from a by 2 to a+limit do 
  >     act:=isprime(i);
  >     if prev and act then lprint(i-2,i) fi; prev:=act
  >   od
  > end:

  > twinprimes(10^9+1, 1000);

  1000000007    1000000009
  1000000409    1000000411
  1000000931    1000000933

To find the prime neighbours of an arbitrary number we can use the functions prevprime and nextprime, too.

  > b:=12345678901234567890:
  > prevprime(b), nextprime(b);

$$12345678901234567879, \,12345678901234567891$$

HEJ, HU ISSN 1418-7108 Manuscript no.: ANM-000926-A