Prime Number

A prime number is a Positive Integer $p$ which has no Divisors other than 1 and $p$ itself. Although the number 1 used to be considered a prime, it requires special treatment in so many definitions and applications involving primes greater than or equal to 2 that it is usually placed into a class of its own. Since 2 is the only Even prime, it is also somewhat special, so the set of all primes excluding 2 is called the ``Odd Primes.'' The first few primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, ... (Sloane's A000040, Hardy and Wright 1979, p. 3). Positive Integers other than 1 which are not prime are called Composite.

The function which gives the number of primes less than a number $n$ is denoted $\pi(n)$ and is called the Prime Counting Function. The theorem giving an asymptotic form for $\pi(n)$ is called the Prime Number Theorem.

Prime numbers can be generated by sieving processes (such as the Eratosthenes Sieve), and Lucky Numbers, which are also generated by sieving, appear to share some interesting asymptotic properties with the primes.

Many Prime Factorization Algorithms have been devised for determining the prime factors of a given Integer. They vary quite a bit in sophistication and complexity. It is very difficult to build a general-purpose algorithm for this computationally ``hard'' problem, so any additional information which is known about the number in question or its factors can often be used to save a large amount of time. The simplest method of finding factors is so-called ``Direct Search Factorization'' (a.k.a. Trial Division). In this method, all possible factors are systematically tested using trial division to see if they actually Divide the given number. It is practical only for very small numbers.

Because of their importance in encryption algorithms such as RSA Encryption, prime numbers can be important commercial commodities. In fact, Roger Schlafly has obtained U.S. Patent 5,373,560 (12/13/94) on the following two primes (expressed in hexadecimal notation):

$\tt\qquad 98A3DF52 AEAE9799 325CB258 D767EBD1 F4630E9B$
$\tt\qquad 9E21732A 4AFB1624 BA6DF911 466AD8DA 960586F4$
$\tt\qquad A0D5E3C3 6AF09966 0BDDC157 7E54A9F4 02334433$
$\tt\qquad ACB14BCB$

and

$\tt\qquad 93E8965D AFD9DFEC FD00B466 B68F90EA 68AF5DC9$
$\tt\qquad FED91527 8D1B3A13 7471E655 96C37FED 0C7829FF$
$\tt\qquad 8F8331F8 1A270043 8ECDCC09 447DC397 C685F397$
$\tt\qquad 294F722B CC484AED F28BED25 AAAB35D3 5A65DB1F$
$\tt\qquad D62C9D7B A55844FE B1F9401E 67134093 3EE43C54$
$\tt\qquad E4DC4594 00D7AD61 248B83A2 624835B3 1FFF2D95$
$\tt\qquad 95A5B90B 276E44F9.$

The Fundamental Theorem of Arithmetic states that any Positive Integer can be represented in exactly one way as a Product of primes. Euclid's Second Theorem demonstrated that there are an infinite number of primes. However, it is not known if there are an infinite number of primes of the form $x^2+1$, whether there are an Infinite number of Twin Primes, or if a prime can always be found between $n^2$ and $(n+1)^2$.

Prime numbers satisfy many strange and wonderful properties. For example, there exists a Constant $\theta\approx 1.3064$ known as Mills' Constant such that

$$\left\lfloor{\theta^{3^n}}\right\rfloor ,$$ (1)

where $\left\lfloor{x}\right\rfloor$ is the Floor Function, is prime for all $n\geq 1$. However, it is not known if $\theta$ is Irrational. There also exists a Constant $\omega\approx 1.9287800$ such that

$$\left\lfloor{{\underbrace{{2}^{{2}^{\cdot^{\cdot^{\cdot^2}}}... ...raise2pt\hbox{$\scriptscriptstyle {\,\omega}$}}}\right\rfloor$$ (2)

(Ribenboim 1996, p. 186) is prime for every $n\geq 1$.

Explicit Formulas exist for the $n$th prime both as a function of $n$ and in terms of the primes 2, ..., $p_{n-1}$ (Hardy and Wright 1979, pp. 5-6; Guy 1994, pp. 36-41). Let

$$F(j)=\left\lfloor{\cos^2\left[{\pi {(j-1)!+1\over j}}\right]}\right\rfloor$$ (3)

for integral $j>1$, and define $F(1)=1$, where $\left\lfloor{x}\right\rfloor$ is again the Floor Function. Then

$$p_n = 1+\sum_{m=1}^{2^n} \left\lfloor{\left\lfloor{n\over \sum_{j=1}^m F(j)}\right\rfloor ^{1/n}}\right\rfloor$$ (4)

$$= 1+\sum_{m=1}^{2^n} \left\lfloor{\left\lfloor{n\over 1+\pi(m)}\right\rfloor ^{1/n}}\right\rfloor ,$$ (5)

where $\pi(m)$ is the Prime Counting Function. It is also true that

$$p_{n+1}=1+p_n+F(p_n+1)+F(p_n+1)F(p_n+2)+\prod_{j=1}^p F(p_n+j)$$ (6)

(Ribenboim 1996, pp. 180-182). Note that the number of terms in the summation to obtain the $n$th prime is $2^n$, so these formulas turn out not to be practical in the study of primes. An interesting Infinite Product formula due to Euler which relates $\pi$ and the $n$th Prime $p_n$ is

$$\pi = {2\over\prod_{i=n}^\infty \left[{1+{\sin({\textstyle{1\over 2}}\pi p_n)\over p_n}}\right]}$$ (7)

$$= {2\over\prod_{i=n}^\infty \left[{1+{(-1)^{(p_n-1)/2}\over p_n}}\right]}$$ (8)

(Blatner 1997). Conway (Guy 1983, Conway and Guy 1996, p. 147) gives an algorithm for generating primes based on 14 fractions, but it is actually just a concealed version of a Sieve.

Some curious identities satisfied by primes $p$ are

$$\sum_{k=1}^{p-1} \left\lfloor{k^3\over p}\right\rfloor ={(p-2)(p-1)(p+1)\over 4}$$ (9)

$$\sum_{k=1}^{(p-1)(p-2)} \left\lfloor{(kp)^{1/3}}\right\rfloor = {\textstyle{1\over 4}}(3p-5)(p-2)(p-1)$$ (10)

(Doster 1993),

$$\prod_{p{\rm\ prime}} {p^2+1\over p^2-1}={5\over 2}$$ (11)

(Le Lionnais 1983, p. 46),

$$\sum_{k=1}^\infty x^k\ln k=\sum_{p{\rm\ prime}} \sum_{k=1}^\infty {x^{p^k}\over 1-x^{p^k}},$$ (12)

and

$$\sum_{k=1}^\infty (-1)^{k-1}e^{-kx}\ln k = -\ln 2\sum_{k=1}^... ...ptstyle odd\ prime} \ln p\sum_{k=1}^\infty {1\over e^{p^kx}+1}$$ (13)

(Berndt 1994, p. 114).

It has been proven that the set of prime numbers is a Diophantine Set (Ribenboim 1991, pp. 106-107). Ramanujan also showed that

$${d\pi(x)\over dx}\sim {1\over x\ln x}\sum_{n=1}^\infty {\mu(n)\over n}x^{1/n},$$ (14)

where $\pi(x)$ is the Prime Counting Function and $\mu(n)$ is the Möbius Function (Berndt 1994, p. 117). B. M. Bredihin proved that

$$f(x,y)=x^2+y^2+1$$ (15)

takes prime values for infinitely many integral pairs $(x,y)$ (Honsberger 1976, p. 30). In addition, the function

$$f(x,y)={\textstyle{1\over 2}}(y-1)\left\lfloor{\vert B^2(x,y)-1\vert-(B^2(x,y)-1)}\right\rfloor +2,$$ (16)

where

$$B(x,y)=x(y+1)-(y!+1),$$ (17)

$y!$ is the Factorial, and $\left\lfloor{x}\right\rfloor$ is the Floor Function, generates only prime numbers for Positive integral arguments. It not only generates every prime number, but generates Odd primes exactly once each, with all other values being 2 (Honsberger 1976, p. 33). For example,

$$f(1,2) = 3$$ (18)

$$f(5,4) = 5$$ (19)

$$f(103,6) = 7,$$ (20)

with no new primes generated for $x,y\leq 1000$.

For $n$ an Integer $\geq 2$, $n$ is prime Iff

$${n-1\choose k}\equiv (-1)^k\ \left({{\rm mod\ } {n}}\right)$$ (21)

for $k=0$, 1, ..., $n-1$ (Deutsch 1996).

Cheng (1979) showed that for $x$ sufficiently large, there always exist at least two prime factors between $(x-x^\alpha)$ and $x$ for $\alpha\geq 0.477\ldots$ (Le Lionnais 1983, p. 26). Let $f(n)$ be the number of decompositions of $n$ into two or more consecutive primes. Then

$$\lim_{x\to\infty} {1\over x}\sum_{n=1}^x f(n)=\ln 2$$ (22)

(Moser 1963, Le Lionnais 1983, p. 30). Euler showed that the sum of the inverses of primes is infinite

$$\sum_{p{\rm\ prime}} {1\over p}=\infty$$ (23)

(Hardy and Wright 1979, p. 17), although it diverges very slowly. The sum exceeds 1, 2, 3, ... after 3, 59, 361139, ... (Sloane's A046024) primes, and its asymptotic equation is

$$\sum_{\scriptstyle p=2\atop\scriptstyle p{\rm\ prime}}^x {1\over p}=\ln\ln x+B_1+o(1),$$ (24)

where $B_1$ is Mertens Constant (Hardy and Wright 1979, p. 351). Dirichlet showed the even stronger result that

$$\sum_{\scriptstyle{\rm prime\ }p\equiv b\ \left({{\rm mod\ } {a}}\right)\atop\scriptstyle (a,b)=1} {1\over p}=\infty$$ (25)

(Davenport 1980, p. 34).

Despite the fact that $\sum 1/p$ diverges, Brun showed that

$$\sum_{\scriptstyle p\atop \scriptstyle p+2{\rm\ prime}}{1\over p}=B<\infty,$$ (26)

where $B$ is Brun's Constant. The function defined by

$$P(n)\equiv \sum_p {1\over p^n}$$ (27)

taken over the primes converges for $n>1$ and is a generalization of the Riemann Zeta Function known as the Prime Zeta Function.

The probability that the largest prime factor of a Random Number $x$ is less than $\sqrt{x}$ is ln 2 (Beeler et al. 1972, Item 29). The probability that two Integers picked at random are Relatively Prime is $[\zeta(2)]^{-1}=6/\pi^2$, where $\zeta(x)$ is the Riemann Zeta Function (Cesaro and Sylvester 1883). Given three Integers chosen at random, the probability that no common factor will divide them all is

$$[\zeta(3)]^{-1}\approx 1.20206^{-1} \approx 0.831907,$$ (28)

where $\zeta(3)$ is Apéry's Constant. In general, the probability that $n$ random numbers lack a $p$th Power common divisor is $[\zeta(np)]^{-1}$ (Beeler et al. 1972, Item 53).

Large primes include the large Mersenne Primes, Ferrier's Prime, and $391581\cdot 2^{216193}-1$ (Cipra 1989). The largest known prime as of 1998, is the Mersenne Prime $2^{3021377}-1$.

Primes consisting of consecutive Digits (counting 0 as coming after 9) include 2, 3, 5, 7, 23, 67, 89, 4567, 78901, ... (Sloane's A006510).

See also Adleman-Pomerance-Rumely Primality Test, Almost Prime, Andrica's Conjecture, Bertrand's Postulate, Brocard's Conjecture, Brun's Constant, Carmichael's Conjecture, Carmichael Function, Carmichael Number, Chebyshev Function, Chebyshev-Sylvester Constant, Chen's Theorem, Chinese Hypothesis, Composite Number, Composite Runs, Copeland-Erdös Constant, Cramer Conjecture, Cunningham Chain, Cyclotomic Polynomial, de Polignac's Conjecture, Dirichlet's Theorem, Divisor, Erdös-Kac Theorem, Euclid's Theorems, Feit-Thompson Conjecture, Fermat Number, Fermat Quotient, Ferrier's Prime, Fortunate Prime, Fundamental Theorem of Arithmetic, Gigantic Prime, Giuga's Conjecture, Goldbach Conjecture, Good Prime, Grimm's Conjecture, Hardy-Ramanujan Theorem, Irregular Prime, Kummer's Conjecture, Lehmer's Problem, Linnik's Theorem, Long Prime, Mersenne Number, Mertens Function, Miller's Primality Test, Mirimanoff's Congruence, Möbius Function, Palindromic Number, Pépin's Test, Pillai's Conjecture, Poulet Number, Primary, Prime Array, Prime Circle, Prime Factorization Algorithms, Prime Number of Measurement, Prime Number Theorem, Prime Power Symbol, Prime String, Prime Triangle, Prime Zeta Function, Primitive Prime Factor, Primorial, Probable Prime, Pseudoprime, Regular Prime, Riemann Function, Rotkiewicz Theorem, Schnirelmann's Theorem, Selfridge's Conjecture, Semiprime, Shah-Wilson Constant, Sierpinski's Composite Number Theorem, Sierpinski's Prime Sequence Theorem, Smooth Number, Soldner's Constant, Sophie Germain Prime, Titanic Prime, Totient Function, Totient Valence Function, Twin Primes, Twin Primes Constant, Vinogradov's Theorem, von Mangoldt Function, Waring's Conjecture, Wieferich Prime, Wilson Prime, Wilson Quotient, Wilson's Theorem, Witness, Wolstenholme's Theorem, Zsigmondy Theorem

References

Prime Numbers

Beeler, M.; Gosper, R. W.; and Schroeppel, R. HAKMEM. Cambridge, MA: MIT Artificial Intelligence Laboratory, Memo AIM-239, Feb. 1972.

Berndt, B. C. ``Ramanujan's Theory of Prime Numbers.'' Ch. 24 in Ramanujan's Notebooks, Part IV. New York: Springer-Verlag, 1994.

Blatner, D. The Joy of Pi. New York: Walker, p. 110, 1997.

Caldwell, C. ``Largest Primes.'' http://www.utm.edu/research/primes/largest.html.

Cheng, J. R. ``On the Distribution of Almost Primes in an Interval II.'' Sci. Sinica 22, 253-275, 1979.

Cipra, B. A. ``Math Team Vaults Over Prime Record.'' Science 245, 815, 1989.

Conway, J. H. and Guy, R. K. The Book of Numbers. New York: Springer-Verlag, p. 130, 1996.

Courant, R. and Robbins, H. ``The Prime Numbers.'' §1 in Supplement to Ch. 1 in What is Mathematics?: An Elementary Approach to Ideas and Methods, 2nd ed. Oxford, England: Oxford University Press, pp. 21-31, 1996.

Davenport, H. Multiplicative Number Theory, 2nd ed. New York: Springer-Verlag, 1980.

Deutsch, E. ``Problem 1494.'' Math. Mag. 69, 143, 1996.

Dickson, L. E. ``Factor Tables, Lists of Primes.'' Ch. 13 in History of the Theory of Numbers, Vol. 1: Divisibility and Primality. New York: Chelsea, pp. 347-356, 1952.

Doster, D. Problem 10346. Amer. Math. Monthly 100, 951, 1993.

Giblin, P. J. Primes and Programming: Computers and Number Theory. New York: Cambridge University Press, 1994.

Guy, R. K. ``Conway's Prime Producing Machine.'' Math. Mag. 56, 26-33, 1983.

Guy, R. K. ``Prime Numbers,'' ``Formulas for Primes,'' and ``Products Taken Over Primes.'' Ch. A, §A17, and §B48 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 3-43, 36-41 and 102-103, 1994.

Hardy, G. H. Ch. 2 in Ramanujan: Twelve Lectures on Subjects Suggested by His Life and Work, 3rd ed. New York: Chelsea, 1978.

Hardy, G. H. and Wright, E. M. ``Prime Numbers'' and ``The Sequence of Primes.'' §1.2 and 1.4 in An Introduction to the Theory of Numbers, 5th ed. Oxford, England: Clarendon Press, pp. 1-4, 1979.

Honsberger, R. Mathematical Gems II. Washington, DC: Math. Assoc. Amer., p. 30, 1976.

Kraitchik, M. ``Prime Numbers.'' §3.9 in Mathematical Recreations. New York: W. W. Norton, pp. 78-79, 1942.

Le Lionnais, F. Les nombres remarquables. Paris: Hermann, pp. 26, 30, and 46, 1983.

Moser, L. ``Notes on Number Theory III. On the Sum of Consecutive Primes.'' Can. Math. Bull. 6, 159-161, 1963.

Pappas, T. ``Prime Numbers.'' The Joy of Mathematics. San Carlos, CA: Wide World Publ./Tetra, pp. 100-101, 1989.

Ribenboim, P. The Little Book of Big Primes. New York: Springer-Verlag, 1991.

Ribenboim, P. The New Book of Prime Number Records. New York: Springer-Verlag, 1996.

Riesel, H. Prime Numbers and Computer Methods for Factorization, 2nd ed. Boston, MA: Birkhäuser, 1994.

Schinzel, A. and Sierpinski, W. ``Sur certains hypothèses concernant les nombres premiers.'' Acta Arith. 4, 185-208, 1958.

Schinzel, A. and Sierpinski, W. Erratum to ``Sur certains hypothèses concernant les nombres premiers.'' Acta Arith. 5, 259, 1959.

Sloane, N. J. A. Sequences A046024, A000040/M0652, and A006510/M0679, in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.

Wagon, S. ``Primes Numbers.'' Ch. 1 in Mathematica in Action. New York: W. H. Freeman, pp. 11-37, 1991.

Zaiger, D. ``The First 50 Million Prime Numbers.'' Math. Intel. 0, 221-224, 1977.