32
$\begingroup$

Prime numbers are numbers with no factors other than one and itself.

Factors of a number are always lower or equal to than a given number; so, the larger the number is, the larger the pool of "possible factors" that number might have.

So the larger the number, it seems like the less likely the number is to be a prime.

Surely there must be a number where, simply, every number above it has some other factors. A "critical point" where every number larger than it simply will always have some factors other than one and itself.

Has there been any research as to finding this critical point, or has it been proven not to exist? That for any $n$ there is always guaranteed to be a number higher than $n$ that has no factors other than one and itself?

  • 4
    Is the question bad because it is too basic? Many questions already here can be answered by a check of wikipedia; in fact, many questions on the Trilogy Sites could be answered by wikipedia as well.2010-07-21
  • 7
    I think that some effort should be necessary on the part of the person asking the question...2010-07-21
  • 12
    +1 I think this is a good question. We are going to see a *lot* of questions that can be answered with a trip to Google or Wikipedia, especially during the beta, but I think that is a *good* thing. The ultimate goal is to build a body of knowledge on the topic of mathematics in question/answer format. This question, and others like it, are part of that goal. In the future, someone may want an answer to this question and when Google leads them here, they will say "hey, what a great website", and sign up `:)`2010-07-21
  • 3
    Mathunderflow should be like mathoverflow for lower level problems.2010-07-21
  • 1
    Googling "is there a largest prime number" or "how many primes are there" or "are there infinitely many primes" or "are there finitely many primes" all lead to simple answers to this question at the very top of the results list. Furthermore, the infinitude of primes is nearly the first thing mentioned in the Wikipedia article for Prime Number.2010-07-21
  • 0
    IMNHO it's not a problem of "you may just google the answer". I would accept without a problem a question "does it exist a largest prime number?" (and give the classical Euclidean answer), but the formulation of this question seems rather suspicious.2010-07-21
  • 7
    You know, after sleeping on it, I've realized that this question is a pretty bad question. I was trying to find the borderline between acceptably easy and unacceptably easy, and I might strayed slightly.2010-07-22
  • 0
    I think this a great question. The answer is on Google and Wikipedia and elsewhere, but the explanations you found out there are probably hard to understand. There are some people here who could answer this in really nice, plain, understandable language. +1 for sure.2010-09-25
  • 0
    He never said "in the integers with the usual operations" so maybe he means: Is there a setting where there is a largest prime ...2011-06-07
  • 2
    @97832123 "Mathunderflow should be like mathoverflow for lower level problems." And I thought the people in this site disliked both this phrase and the attitude that the problems here are of lower level? :-)2011-08-01
  • 0
    @Justin I think any question that shows the person is thinking and not simply accepting something on faith is a good one-no matter how simple the answer turns out to be.2011-09-08

10 Answers 10

43

Euclid's famous proof is as follows: Suppose there is a finite number of primes. Let $x$ be the product of all of these primes. Then look at $x+1$. It is clear that $x$ is coprime to $x+1$. Therefore, no nontrivial factor of $x$ is a factor of $x+1$, but every prime is a factor of $x$. By the fundamental theorem of arithmetic, $x+1$ admits a prime factorization, and by the above remark, none of these prime factors can be a factor of $x$, but $x$ is the product of all primes. This is a contradiction.

  • 2
    The proof also works in the ring of polynomials over a finite field.2010-07-21
  • 1
    Quantity is better than quality, my answer is better. :D2010-07-21
  • 0
    @BBischof: =p why don't you come back to IRC?2010-07-21
  • 8
    Note: Euclid's original proof was *not* by way of contradiction, although many authors mistakenly claim so. For much further discussion see e.g. Hardy & Woodgold, "Prime Simplicity" [1] http://www.springerlink.com/content/m0t8727288823ug5/ [2] http://www.artofproblemsolving.com/Forum/download/file.php?id=270702010-07-29
  • 12
    Yeah, Hardy & Woodgold's paper should be required reading for how historical errors propagate from book to book (even when all it takes is a look at the source!). Euclid's original proof and statement are simpler: It shows that given any finite list of primes $p_1, \dots, p_k$, we can extend the list with a prime factor of $p_1\dots p_k +1$. We don't have to assume there is a largest prime, or use contradiction. (Also, we don't need the fundamental theorem of arithmetic, just the simpler statement that every number has a prime factor — provable with descent/induction.)2010-08-04
  • 1
    It deserves to be better known that Euclid's constructive proof generalizes widely, e.g. see my generalization to fewunit rings http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1209616#p1209616 http://google.com/groups?selm=y8zk5f3rn4e.fsf%40nestle.csail.mit.edu2010-08-05
  • 0
    Note: I've added my fewunits generalization of Euclid's proof to my answer here.2011-09-08
  • 0
    Personally,I love Furstenberg's proof using point set topology and plan to use it as the jumping off point for my first real research project.2011-09-08
  • 0
    Your proof can be modified so as to avoid the unique factorization theorem: If $n >1$ let m be the least natural number greater than $1$ that divides $n.$ Then $m$ is prime. So every $n>1$ is divisible by a prime (a prime $ >1,$ considering the first sentence of the Q.) So $x+1$ is divisible by a prime that is not equal to any prime, a paradox.2016-12-14
  • 0
    The first chapter of the book Prime Number Records consists of about 23 different proofs that there is no largest prime.2016-12-14
38

Below are a couple noteworthy variations on Euclid's classic proof that there are infinitely many primes. The first is a simplification and the second is a generalization to rings with few units.

THEOREM $\rm\ \ N (N+1) \;$ has a larger set of prime factors than does $\:\rm N > 0\:$.

Proof $\ $ $\rm N+1 > 1\,$ so it has a prime factor $\rm P$ (e.g. its least factor $> 1)$. $\,\rm N$ is coprime to $\rm N+1\,$ so $\rm P$ can't divide $\rm N$ (else $\rm\: P$ divides $\rm N+1\:$ and $\rm N$ so also their difference $\rm N+1 - N = 1)$. So the prime factors of $\rm\: N(N+1)$ include all those of $\rm N$ and at least one prime $\rm P$ not dividing $\rm N$.

COROLLARY $\ \ $ There are infinitely many primes.

Proof $\, $ Iterating $\rm\, N\to N (N+1)\, $ yields integers with an unbounded number of prime factors.

Below, generalizing Euclid's classic argument, is a simple proof that an infinite ring has infinitely many maximal (so prime) ideals if it has fewer units than elements (i.e. smaller cardinality). The key idea is that Euclid's construction of a new prime generalizes from elements to ideals, i.e. given some maximal ideals $\rm P_1,\ldots,P_k$ then a simple pigeonhole argument employing $\rm CRT$ implies that $\rm 1 + P_1\cdots P_k$ contains a nonunit, which lies in some maximal ideal $\rm P$ which, by construction, is comaximal (so distinct) from the prior max ideals $\rm P_i\:.\:$ Below is the full proof, excerpted from from some of my old sci.math/AAA/AoPS posts.

THEOREM $\ $ An infinite ring $\rm R$ has infinitely many max ideals if it has fewer units $\rm U = U(R)$ than it has elements, i.e. $\rm\:|U| < |R|$.

Proof $\rm\ \ R$ has a max ideal $\rm P_1\:,\:$ since the nonunit $\rm\: 0\:$ lies in some max ideal.
Inductively, suppose $\rm P_1,\ldots,P_k$ are maximal ideals in $\rm R$, with product $\rm J.$

$\rm Case\ 1: \; 1 + J \not\subset U\:.\:$ So $\rm 1 + J$ contains a nonunit $\rm p,$ lying in some max ideal $\rm P.$
It's new: $\rm\: P \neq P_i\:$ since $\rm\: P + P_i = 1\:$ via $\rm\: p \in P,\ 1 - p \in J \subset P_i$

$\rm Case\ 2: \; 1 + J \subset U$ is impossible by the following $\,$ pigeonhole $\:$ argument. $\rm R/J = R_1 \times \cdots \times R_k,\ R_i = R/P_i\:$ by the Chinese Remainder Theorem.
We deduce that $\rm\ |U(R/J)| \leq |U|\ $ because $\rm\ uv \in 1 + J \subset U \Rightarrow u \in U.$
Thus $\rm|U(R_i)| \leq |U(R/J)| \leq |U|\:$ via the injection $\rm u \mapsto (1,1,\ldots,u,\ldots,1,1).$
$\rm R_i$ field $\rm\: \Rightarrow\ |R| > 1 + |U| \geq |R_i|,$ and also $\rm|J| \leq |U| < |R|$ via $\rm 1 + J \subset U.$
Therefore $\rm|R| = |R/J|\ |J| = |R_1|\ \cdots |R_k|\ |J|\:$ yields the contradiction that
the infinite $\rm|R|$ is a finite product of smaller cardinals. $\ \ $ QED

I recall the pleasure of discovering this "fewunit" generalization of Euclid's proof and other related theorems while reading Kaplansky's classic textbook Commutative Rings as an MIT undergrad. There Kaplansky presents a simpler integral domain version as exercise $8$ in Section $1$-$1\:,\:$ namely

(This exercise is offered as a modernization of Euclid's theorem on the infinitude of primes.) Prove that an infinite integral domain with with a finite number of units has an infinite number of maximal ideals.

I highly recommend Kap's classic textbook to everyone interested in mastering commutative ring theory. In fact I highly recommend everything by Kaplansky - it is almost always very insightful and elegant. Learn from the masters! For more about Kaplansky see this interesting NAMS paper which includes quotes from many eminent mathematicians (Bass, Eisenbud, Kadison, Lam, Rotman, Swan, etc).

I liked the algebraic way of looking at things. I'm additionally fascinated when the algebraic method is applied to infinite objects. $\ $--Irving Kaplansky

NOTE $\ $ The reader familiar with the Jacobson radical may note that it may be employed to describe the relationship between the units in $\rm R$ and $\rm R/J\:$ used in the above proof. Namely

THEOREM $\ $ TFAE in ring $\rm\:R\:$ with units $\rm\:U,\:$ ideal $\rm\:J,\:$ and Jacobson radical $\rm\:Jac(R)\:.$

$\rm(1)\quad J \subseteq Jac(R),\quad $ i.e. $\rm\:J\:$ lies in every max ideal $\rm\:M\:$ of $\rm\:R\:.$

$\rm(2)\quad 1+J \subseteq U,\quad\ \ $ i.e. $\rm\: 1 + j\:$ is a unit for every $\rm\: j \in J\:.$

$\rm(3)\quad I\neq 1\ \Rightarrow\ I+J \neq 1,\qquad\ $ i.e. proper ideals survive in $\rm\:R/J\:.$

$\rm(4)\quad M\:$ max $\rm\:\Rightarrow M+J \ne 1,\quad $ i.e. max ideals survive in $\rm\:R/J\:.$

Proof $\: $ (sketch) $\ $ With $\rm\:i \in I,\ j \in J,\:$ and max ideal $\rm\:M,$

$\rm(1\Rightarrow 2)\quad j \in all\ M\ \Rightarrow\ 1+j \in no\ M\ \Rightarrow\ 1+j\:$ unit.

$\rm(2\Rightarrow 3)\quad i+j = 1\ \Rightarrow\ 1-j = i\:$ unit $\rm\:\Rightarrow I = 1\:.$

$\rm(3\Rightarrow 4)\ \:$ Let $\rm\:I = M\:$ max.

$\rm(4\Rightarrow 1)\quad M+J \ne 1 \Rightarrow\ J \subseteq M\:$ by $\rm\:M\:$ max.

  • 0
    I have not seen this, it is as you say the essence of the Euclid proof. Also, a good exercise for fresh students.2010-09-25
  • 0
    @AD.: Yes, it's very strange that this proof is rarely if ever mentioned in the literature. It must be very old but I don't know the history. Does anyone have any historical information?2010-09-25
  • 0
    @Bill Dubuque : You use equality or isomorphic in your chineese remainder theorem under case 2 ; but how do you know that the max. ideals are co-maximal ?2015-04-20
  • 0
    @BillDubuque : And I don't understand how $|U(R_i)| \le |U(R/J)|$ via the injection , injection from where to where ? Please help .2015-04-20
  • 0
    @SaunDev The max ideals are presumed distinct, i.e. $\,\rm i\neq j\,\Rightarrow\, M_i\neq M_j.\,$ Distinct max ideals are comaximal. Note that the displayed injection is a map from $\rm\,U(R_i)\,$ to $\,\rm U(R/J)\ $ which maps a unit of the factor $\,\rm R_i\,$ into the product $\,\rm R/J = R_1\times\cdots \times R_k\ \ $2015-04-20
  • 0
    @BillDubuque : Thanks , really great2015-04-22
12

No there is not, here is a collection of proofs;

http://math.mit.edu/~ssam/writings/primes.pdf

  • 0
    The last proof in Sam's handout seems circular to me. A PID is a Jacobson domain iff it has infinitely many primes (c.f. Theorem 117 and Proposition 131 of http://math.uga.edu/~pete/integral.pdf). I consulted Lemma 4.20 of Eisenbud and again do not see how to apply it without knowing there are infinitely many primes.2010-08-11
  • 1
    @Pete, I have not worked carefully through all of the proofs there. I would suggest you email him, you can find his website at MIT and his email on there(I don't want to put it here in case of bots). I am sure he would appreciate your comments. In the past I have emailed him and gotten a good response.2010-08-11
  • 0
    @BB: Yes, I'll email him when I get the chance. I wanted to post the comment here so as to allow people the chance to correct me, in which case I wouldn't want to bother the author.2010-08-11
  • 0
    @PLC np, I just haven't thought about it yet.2010-08-11
  • 8
    I heard back from Steven Sam. He agrees with me and will make appropriate modifications.2010-08-11
12

Here's a really nice proof that there are an infinite number of primes:

$\prod(1-p_i^{-2})^{-1} = \zeta(2) = \pi^2/6$.

Since $\pi$ is transcendental, the RHS is irrational. Therefore there must be an infinite number of terms in the product on the left.

  • 1
    However, proving transcendence of $\pi$ most probably requires proving infinitude of primes. See http://mathoverflow.net/questions/21367/2012-01-23
11

$$\sum_p \frac{1}{p}=\infty$$ Here is a link


Edit: If there was finitely many primes, then the sum would be finite.

7

According to XKCD, we have the following Haiku:

Top Prime's Divisors'
Product (Plus one)'s factors are...?
Q.E.D B@%&$

I wonder if we can edit it to make it correct

  • 0
    What is the rule on language? Should I edit the quote?2010-07-21
  • 0
    Wrong. Wrong. Wrong.2010-07-21
  • 0
    @Harry: What is wrong?2010-07-21
  • 0
    @Harry: How so?2010-07-21
  • 0
    Read what you wrote.2010-07-21
  • 3
    Actually, rereading the comic, it is also wrong.2010-07-21
  • 0
    @Harry: How come?2010-07-21
  • 0
    It's a mangled version of the proof I gave.2010-07-21
  • 0
    @Harry: But its in Haiku, so its awesome!2010-07-21
  • 2
    but it is wrong nevertheless.2010-07-21
  • 2
    @mau: I still don't get the mistake?2010-07-21
  • 0
    I wouldn't call it a rigorous proof, but it seems pretty much correct.2010-07-30
  • 0
    As far as editing the text, I'd be cautious...most people will probably be okay with it, but it doesn't take too many people to flag it (6, I think) before it becomes a -100 hit.2010-07-30
  • 3
    It *is* wrong. The divisors of any prime are just 1 and itself, so "Top Prime's Divisors' Product" is just of the form $p_k+1$. Maybe if it said "All primes' divisors' product…" (with the "divisors" being redundant), it would be correct. As long as the apostrophe is *inside* "prime's", it's wrong.2010-08-04
6

Another proof is:

Consider the numbers $$9^{2^n} + 1, \\ \\ n = 1,2,\dots$$

Now if $$9^{2^n} + 1 = 0 \mod p$$ then we have that, for $ m > n$ that

$$9^{2^m} + 1 = (9^{2^n})^{2^{m-n}} + 1 = (-1)^{2^{m-n}} + 1 = 1+1 = 2 \mod p$$

Thus if one term of the sequence is divisible by a prime, none of the next terms are divisible by that prime, i.e. if you write out the factors of the terms of the sequence, each term of this sequence gives rise to a prime not seen before!

As a curiosity, it can be shown that each number in the sequence has at least one prime factor > 40. See this question on this very site: Does $9^{2^n} + 1$ always have a prime factor larger than $40$?

  • 4
    So not only are there infinitely many primes, there are infinitely many primes > 40? :-)2010-10-15
  • 9
    @Steve: Yes, as they say, when you are over 40, you are past your prime :-)2010-10-15
5

Now that this question has been bumped up, I feel like posting the other somewhat famous proof that they are infinitely many primes: Consider the Fermat numbers $F_n = 2^{2^n} + 1$. It is an easy exercise to see that the gcd of any two Fermat numbers is $1$. As each number has at least one prime factor, picking for each $F_n$ a factor $p_n$ gives an infinite sequence of prime numbers.

This proof is usually attributed to Pólya, but it may well be much older. See this discussion of its history on Math Overflow.

  • 0
    In fact, I think there's one more conceptual message in the proof, namely: _There are infinitely many prime numbers iff there exists an infinite set of numbers that are pairwise relatively prime_. You indicated one direction of the proof. For the other direction, the infinite set of primes itself is pairwise relatively prime. :-) Perhaps this connection is why someone thought of this proof?2011-08-01
2

I found this proof on this Chinese website. Here is the translation.

This is a proof with information theory (the proof can be done without information theory, but this is just cool). $\log(n)$ always means $\log_2(n)$

Uniformly pick a integer $N$ between 1 and $n$. We have

$H(N) = \log(n)$

Where $H(x)$ is the entropy function.

$N$ can be represented by $m$ integers $X_1,\ldots,X_m$ uniquely as

$N = p_i^{X_i}$

where $m$ is the amount of primes no larger than $n$.

$H(N) = H(X_1, X_2, \ldots, X_m)$

$H(N) \leq H(X_1)+H(X_2)+\cdots+H(X_m)$

Since $X_i \leq \log(N)$ ($2^{\log_2(N)} = N$), we have

$H(N) \leq m H(\log(N))$

$\frac{\log(n)}{\log(\log(n)+1)} \leq m$

The lhs can increase indefinitely. This even give a bound for the amount of primes smaller than $n$

  • 0
    I don't think you need the use entropy here. Here is a simpler version of the argument which just uses counting. Suppose there were $k$ prime numbers. This means every number $n$ could be uniquely specified by the $k$ exponents in its prime factorization. Each of these exponents is at most $\log n$, so there is a way to map the $k$-tuples $(x_1,\ldots, x_k)$ with each $x_i \in \{ 0, 1, \ldots, \log n \}$ onto $\{1,\ldots,n\}$. But the former set has $(\log n + 1)^k$ elements while the latter set has $n$ elements, and eventually $n > (\log n + 1)^k$ for any $k$.2010-08-04
  • 0
    Why in the world was this edited now? A year after it was last touched?2011-08-01
  • 0
    @mixedmath: One can only speculate!2011-09-17
0

Proof that there is always a higher prime number and therfore an infinite amount of prime numbers:

Mathematicians often hide behind an array of jargonish symbology. We need more proofs like the one I invent here (took me 90 minutes after watching “An infinite Mind” thanks Patel for channeling Ramanujan):

Easiest layman’s proof that there is always a higher prime number than any prime you are given:

Let Y be a prime number of any positive value.

Y!-1 cannot be divided by Y or any other integer lower than Y because those numbers are already factors of Y! and therefore cannot be factors of Y!-1; Therefore any factor of Y!-1 must have a value higher than Y, and yet not be divisible by any other factor lower than Y, which means it must be a prime number higher than Y. So in any case, either Y!-1 is a prime number OR Y!-1 has at least one factor which is prime numbers higher than Y: in either case, there is a higher prime number than Y.

[Y! means 1x2x3x4x5x … all the way up to … Y]