Issue: **How
can we determine large and
very large primes?**

This question on how to determine large and very large primes are most likely asked by most mathematicians, mathematics enthusiasts and students. Even long long time ago, the search for large primes was a focus of study and research. Fortunately, the people in the "gone but not forgotten" era came up with theorems, algorithms and formulas in getting these primes to satisfy the need. Among the contributors were Euclid who developed the Euclidian algorithm, Father Mersenne with his famous Mersenne primes, Eratosthenes with his Sieves of Eratosthenes, Fermat with his Factorization Method and Little Theorem and others like, Gauss, Riemann and Euler who belong to the antique generation. Further studies were also been conducted by enthusiasts in the middle ages and they came up to determine large primes without the help of a computer and mostly, done with their bare hands. To name few of them, they are Anton Felkel, J.P. Kulik, EDF Missal, BK Parody, J.R. Smith and S. Zarantonello, they are the ones who used to publish tables of primes in large numbers as we say it. Most of their work were based on the theorems and correlations from the prototypes of antique generation.

So,* what
is the formula to determine
exact large or very large
primes? *The
answer is that based on the
study, the accurate, exact
and realistic method of
determining large primes is
by the use of

**Sieves of Eratosthenes.**From the name itself you can think that numbers in a range are being sieved or "filtered" and that you can come up with real and exact primes. Here is an example of primes determined by the method in a range less than 100 or 10^2: 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....

Of course, the only problem with this method is that this is very tedious when done by hands especially when expanding in the range to 10^3, 10^4, or 10^n, where: n may be any number greater than 2. However, with the advent of computers, large primes may be generated with the Sieve of Eratosthenes faster than any publishable table may be read (Anderson and Bell, 1997, p.116). This is done by writing a program usually in high level computer language like Turbo Pascal or Turbo C using syntax such as arrays and loops that would command the computer to generate large or very large primes to a certain range. (Note: I am sorry that I could not discuss the programming technique here but I could give the key points in making a flowchart for this program)

The second question one
might ask is: **What
is the use of other theorems
or formulas made by
Mersenne, Fermat or Gauss in determining large primes?**

The
answer to that is the
theorems or formulas made by
these mathematicians were
simple assumptions or estimations to get large
primes and may or may not be
representing exact single
large primes. Let us take
the definition of Mersenne
which states that a Mersenne
number is an integer of the
form M
(n) = 2^n - 1. If a
Mersenne number is prime, it
is called a Mersenne prime
or can be stated this way
"If M
(n) is prime, then n
is a prime." Let us
therefore prove if this is
absolute.

Proof:

__
n__
__2^n - 1 = M (n)__
__Remarks__

1** **
2^1 - 1 = 1
Empty

**
2 ** 2^2 -
1 = 3
2 is prime;
M (n) = 3 prime

**
3
** 2^3 - 1
= 7
3 is prime; M (n)
= 7 prime

4 2^4 - 1 = 15 = 3 x 5 4 is not prime; M (n) = 15 composite

**
5
** 2^5 - 1
= 31
5 is prime; M (n)
= 31 prime

6 2^6 - 1 = 63 = 3^2 x 7 6 is not prime; M (n) = 63 composite

**
7**
2^7 - 1 = 127
7
is prime; so M (n) = 127
prime

8 2^8 - 1 = 255 = 3 x 5 x 17 8 is not prime; M (n) = 255 composite

9 2^9 - 1 = 511 = 7 x 73 9 is not prime; M (n) = 511 composite

10 2^10 - 1 = 1023 = 3 x 11 x 31 10 is not prime; M (n) =1023 composite

**
11** 2^11 -
1 = 2047 = 23 x 89
11 is prime; M (n) = 2047
composite ?

As you can see in the table
above, when n = 11; M (n) =
2047 = 23 x 89 which does
not produce a single prime
but rather composite.
Therefore, we
can deduce
that Mersenne formula is
good only for assumption for
predicting primes but does
not determine exact single
large prime. The same thing
also happens
when we use Fermat number
which is defined as a Fermat
number is an integer of the
form F (n) = 2^2n + 1. If a
Fermat number is prime, it
is called
a prime. Unfortunately, the
Fermat number, F(5) =
4294967297 is divisible by
641 and therefore, not a
prime number and so Fermat
number is also not
absolute.

The third question one might
ask is: *Can we
assume for a large prime
number using the definitions
or theorems made by antique
mathematicians? *

My
answer is yes*. *We
could use the ancient
formulas to predict or test
a certain large number if
its a prime or composite. The method is simple you
just assume a large or very
large number and test it for
primality test. This is done
using the theorem that if
the positive integer n is a
composite integer, then n
has a prime factor p such
that p^2 __<__ n.
This is also similar with
the suggestion made by Dr.
Wilkinson in his conversation
with Mr. Ulric Cajuste
([usepmat_group]primes,1/16/10).
Let us take a proof on this:
ex. determine whether n =
521 is prime?

**
Proof:**

We only
need to consider primes p
that are less than or equal
to 2 for 22^2 = 484 which is
less than 521 according to
the theorem p^2 __<__ n.
If we are to use
23^2 = 529 this would be
greater than 521 and
therefore, does not conform
to the theorem. Hence, we
have to use 22. The primes
less than 22 or equal to
22 are 2, 3, 5, 7, 11, 13,
17, and 19. Trying these
primes to be divided to 521,
we find that none of the
primes divides 521.
Therefore, we can say the
521 is a prime. The only disadvantage with
this method is that we just
have to keep on guessing
numbers until we find
numbers to be prime.

**
Is there another
formula aside from Sieves of
Eratosthenes that could
generate large primes? **Yes,
I have found one but this is subject yet to scrutiny. The
equation looks like this:

P (n) = (2n + 1 - p) d N (n) + p = p (2n + 1 / p)^ d N (n)

where: N if N = 2n + 1 is prime

p if N = 2n + 1 is composite (p: arbitrary prime number)

This equation was formulated
by Prof. S.M.R. Hashemi
Moosavi who claimed that he
solved the problem on prime
number generation. To prove
this formula
would be for our next
discussion.

**
What is the rationale
behind why computer
companies offer prices to
those who can get larger
primes? **I
believe that the rationale behind
offering prices by computer
companies is that 1.) as a
sort of advertisement 2.) to
test their product, say
computer. I am convinced
that the greater weight
falls to the second reason
since computer companies
tend to test their hardware
such as processors or
chipsets if it can perform
long and complex mathematical
operations, including also
is the speed and time to
process instructions. If you
have comments about my
reaction on this topic.
Please feel free to write me
or post a comment.

**
References:**

James A. Anderson and James M Bell, Number Theory with Applications, 1997, Prentice Hall Publishing.

Prof. S.M.R. Hashemi Moosavi, The Discovery of on-to generating function of the prime numbers and its results. (www.primenumbersformula.com)

Date accessed: January 17, 2010.

Ultima_syd, [usepmat_group] primes, 1/16/2010.