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

Prime formulas

The great mathematicians for centuries were trying to give formulas, which would always produce primes, or at least infinitely many primes. For the second part of this question a nice answer was given by the following theorem, which analyses the occurence of prime numbers in arithmetic sequences.
THEOREM 6. (BY DIRICHLET) Let $a$ and $b$ be integer numbers, for which gcd$(a,b)=1$. In this case the sequence $a \cdot k + b$ produces infinitely many primes $(k=1,2,\dots)$.
REMARKS 1. As special cases of Theorem 6., there are infinitely many primes in the form $4 k - 1$, $4k+1$, $6k-1$, $6k+1$. 2. We can rephrase the results as follows: the polynomial $ax + b$ with gcd$(a,b)=1$ produces infinitely many primes. In this context we can formulate some other questions, e.g. a) Is there a polynomial in the form $ax^2 + bx + c$, which produces infinitely many primes? b) Is there a polynomial which always produces prime numbers? In the first case it is easy to prove, that necessary conditions are the irreducibility of the polynomial and gcd$(a,b,c)=1$, but the complete answer is still unknown. To question b), for

$$p(x) = a_n x^n + \dots + a_1 x + a_0 = x ( a_n x^{n-1} + \dots + a_1 ) + a_0$$

if $a_0 = 0$ then $x \vert p(x)$, if $a_0 \ne 0$ then $a_0 \vert p(a_0)$, so the answer is no. This answer was already given by LEGENDRE. There are some polynomials, which seem to be good for a lot of substitution values. EULER has presented the example $x^2 + x +41$, which produces prime numbers for $x=0,1,2, \dots, 39$, however for $x=40, 41$ and other larger values we get composite numbers.

  > p:=x->x^2+x+41:
  > for i from 0 to 45 do
  >   if not isprime(p(i)) then lprint(i,p(i)) fi:
  > od;

  40    1681
  41    1763
  44    2021

In spite of the answer given for part b), theoretically is it possible to give a formula which always produces prime numbers. In 1947 H. MILLS proved, that there exists a real number $A$, for which $[A^{3^n}]$ is always prime for an arbitrary positive integer $n$. However, we do not know the value of this number.
Fermat numbers On the way to find a prime formula, in the 1640s FERMAT drafted, that the numbers $2^{2^n} + 1$ are always prime. He established, that beside the small numbers $2^1 +1, 2^2+1, 2^4+1$ and $2^8+1$ still $2^{16}+1$ is a prime, too. With the number $2^{32}+1$ he and his contemporaries could not reach any result, only in roughly 100 years it was proved by EULER that 641 is a divisor of $2^{2^5} +1$ (with establishing first, that a divisor must be in the form $64 k + 1$). Nowadays we know moreover, that the Fermat numbers for $n=6, 7, \dots 19$ and for more other $n$ values are not primes. We do not know however, if there are another Fermat primes or not. To produce the Fermat numbers in Maple we use the functions fermat or F from the package numtheory.

  > with(numtheory):
  Warning, new definition for order
  > 2^(2^`5`)=F(5), ifactor(fermat(5));

$$2^{(2^{5})}=4294967297, \,(\,{\rm }641)\,(\,{\rm }6700417)$$

  > F(8);

$$11579208923731619542357098500868790785326998466564056403945758400 \backslash$$

$$7913129639937 \hspace{4cm}$$

  > isprime(fermat(8));

$${\it false}$$

REMARKS 1. If $k \ne 2^n$, then $N=2^k +1$ can not be prime. In this case the exponent can be written in the form $k=2^l \cdot m$, where $m$ is an odd number. Thus

$$N = 2^k +1 = 2^{2^l \cdot m} +1 = (2^{2^l})^m + 1^m = (2^{2^l} + 1) ((2^{2^l})^{m-1} -+ \dots + 1^{m-1}),$$

i.e. $N$ is divisible by $(2^{2^l} + 1)$. 2. The Fermat primes play a very important role in geometry in relation with the construction of regular poligons (GAUSS, see e.g. in [9]).
Mersenne numbers After a few years of FERMAT's notice, MERSENNE published his examination relating to the numbers in the form $2^s - 1$. He declared, that these numbers are primes if and only if the exponent is $2, 3, 5, 7, 13, 17, 19, 31, 67, 127$ or $257$ - assuming that the exponent is less equal than $257$ (it was known already in that time, that if $k \vert s$, then $2^k -1 \vert 2^s -1$, thus $2^s-1$ can be only prime, if $s$ is prime). His assertion was not entirely correct, but the first mistake was found only after more than 200 years. É. LUCAS proved in the 1870s that $2^{67} -1$ is not prime. After this some other mistakes were found in the list. The numbers in the form above are called Mersenne numbers, and if they are primes, then their names are Mersenne primes. Nowadays we know more than 30 Mersenne primes. To produce the Mersenne numbers in Maple we use the functions M or mersenne from the package numtheory. The result is the false value if the current Mersenne number is not prime. Using the functions with double parentheses $([i])$ we get exactly the $i$th Mersenne prime.

  > mersenne([9]);

$$2305843009213693951$$

  > 2^9-1, M(9);

$$511, \,{\it false}$$

  > M(127);

$$170141183460469231731687303715884105727$$

With these tools we are immediately able to find some mistakes in MERSENNE's list.

  > 2^67-1, mersenne(67);

$$147573952589676412927, \,{\it false}$$

  > M(89);

$$618970019642690137449562111$$

REMARK In the modern history of mathematics the largest known primes were always Mersenne primes. For example from 1772 through a century the number $2^{31} -1$ (proved by EULER), until 1950 the number $2^{127} - 1$ (proved by É. LUCAS and E. FAUQUEMBERGUE). After this time more Mersenne primes were found with computers, in the past few years since 1985 the largest was $2^{216091} -1$. From 12.01.1994 the largest is $2^{859433}-1$.
Perfect numbers We call a number perfect, if the sum of its divisors - not considering the number itself - is the same as the number (or using the number theoretical function $\sigma(n)$ - the sum of divisors - $\sigma(n)/n = 2$). For example for 6, $1+2+3 = 6$. Such numbers were already investigated by the ancient Greeks, the notion was first mentioned by PLATON. Until the Middle Ages mysterious properties were atributed to perfect numbers. It is not hard to prove, that an even number is perfect if and only if it is in the form of $2^{t-1} \cdot (2^t -1)$, where $(2^t -1)$ is a Mersenne prime. Thus the investigation of perfect numbers is closely related with Mersenne primes. The first 4 perfect numbers were already known by the ancient mathematicians, additional 3 were discovered in the 15-16th century, till MERSENNE's time. We know, that the last digit of an even perfect number must be 6 or 8. Until now nobody could find any odd perfect number, and it seems, that in the near future we have no hope to prove, that an odd perfect number could not exist. In any case, if such number exists, it must be very large... To the examination of the perfect numbers with Maple we can use the function sigma. Fast "control" can be done with the function divisors.

  > c:=2^12*(2^13-1), sigma(c)-c;

$$c := 33550336, \,33550336$$

  > divisors(8192);

$$\{1, \,2, \,4, \,8, \,16, \,32, \,64, \,128, \,512, \,1024, \, 4096, \,256, \,2048, \,8192\}$$

We call a number $k$-times perfect, if $\sigma(n)/n = k$ for $k \in \mathbf{Z}$. These numbers were already investigated by MERSENNE, DESCARTES and FERMAT. Nowadays we know already 334 $k$-times perfect numbers, until the value of $k=8$ ([4]).

  > d:=1476304896, sigma(d)/d;

$$d := 1476304896, \,3$$

With the generalization of this notion we can investigate "perfect-like" numbers, where there is a relation between the sum of divisors not considering the number itself ( $d = \sigma(n) - n$) and the number $n$, such as $d/n = a/b$ or $d = n - a$, where $a$ and $b$ are (positive) integers.

  > e:=3^2*(3^3-1), (sigma(e)-e)/e;

$$e := 234, \frac {4}{3}$$

We have used a Maple program to produce the following results:

Relation	Numbers
$d = n$	6, 28, 496, 8128
$d/n = 2$	120, 672
$d/n = 3$	30240, 32760
$d/n = 4/3$	12, 234
$d/n = 5/3$	84, 270, 1488, 1638, 24384
$d/n = 7/5$	30, 140, 2480, 6200, 40640
$d = n - 1$	1, 2, 4, 8, 16, ...
$d = n - 2$	3, 10, 136

Some results in this tabular are obvious, e.g. in the line $d=n-1$ there are pure 2 powers, since $2^k = 1 + 2 + 2^2 + \dots + 2^{k-1}$.

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