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?

  • 6
    $\begingroup$ 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. $\endgroup$
    – Justin L.
    Commented Jul 21, 2010 at 0:12
  • 9
    $\begingroup$ I think that some effort should be necessary on the part of the person asking the question... $\endgroup$
    – user126
    Commented Jul 21, 2010 at 0:18
  • 14
    $\begingroup$ +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 :) $\endgroup$
    – e.James
    Commented Jul 21, 2010 at 0:40
  • 4
    $\begingroup$ Mathunderflow should be like mathoverflow for lower level problems. $\endgroup$
    – user126
    Commented Jul 21, 2010 at 0:44
  • 11
    $\begingroup$ 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. $\endgroup$
    – Justin L.
    Commented Jul 22, 2010 at 2:03

8 Answers 8


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
    $\begingroup$ The proof also works in the ring of polynomials over a finite field. $\endgroup$ Commented Jul 21, 2010 at 0:29
  • 1
    $\begingroup$ Quantity is better than quality, my answer is better. :D $\endgroup$
    – BBischof
    Commented Jul 21, 2010 at 3:21
  • 16
    $\begingroup$ 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] springerlink.com/content/m0t8727288823ug5 [2] artofproblemsolving.com/Forum/download/file.php?id=27070 $\endgroup$ Commented Jul 29, 2010 at 1:14
  • 13
    $\begingroup$ 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.) $\endgroup$ Commented Aug 4, 2010 at 17:23
  • 1
    $\begingroup$ It deserves to be better known that Euclid's constructive proof generalizes widely, e.g. see my generalization to fewunit rings artofproblemsolving.com/Forum/viewtopic.php?p=1209616#p1209616 google.com/groups?selm=y8zk5f3rn4e.fsf%40nestle.csail.mit.edu $\endgroup$ Commented Aug 5, 2010 at 13:53

Below are two 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 (= invertibles).

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 maximal 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.\:$ Thus $\rm 1 + J$ contains a nonunit $\rm p,\,$ lying in a 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 $\,\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.

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 anyone seeking to master 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 $ $ Readers 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.

  • $\begingroup$ I have not seen this, it is as you say the essence of the Euclid proof. Also, a good exercise for fresh students. $\endgroup$ Commented Sep 25, 2010 at 19:01
  • $\begingroup$ @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? $\endgroup$ Commented Sep 25, 2010 at 19:05
  • $\begingroup$ @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 ? $\endgroup$
    – user228168
    Commented Apr 20, 2015 at 15:44
  • $\begingroup$ @BillDubuque : And I don't understand how $|U(R_i)| \le |U(R/J)|$ via the injection , injection from where to where ? Please help . $\endgroup$
    – user228168
    Commented Apr 20, 2015 at 15:51
  • 1
    $\begingroup$ @algebra.And.analysis Yes. in general-level math forums like this, I use the convention that rings are commutative (and associative) by default (unless the context obviously implies otherwise), cf. this meta thread $\endgroup$ Commented Nov 20, 2020 at 19:27

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.


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

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


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
    $\begingroup$ So not only are there infinitely many primes, there are infinitely many primes > 40? :-) $\endgroup$ Commented Oct 15, 2010 at 22:05
  • 11
    $\begingroup$ @Steve: Yes, as they say, when you are over 40, you are past your prime :-) $\endgroup$
    – Aryabhata
    Commented Oct 15, 2010 at 22:50

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.

  • $\begingroup$ 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? $\endgroup$
    – Srivatsan
    Commented Aug 1, 2011 at 2:08
  • $\begingroup$ This proof was given by Goldbach first in a letter to Euler on 20/31 July,1730. $\endgroup$ Commented May 28, 2020 at 12:12

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

  • $\begingroup$ What is the rule on language? Should I edit the quote? $\endgroup$
    – Casebash
    Commented Jul 21, 2010 at 0:35
  • 3
    $\begingroup$ Actually, rereading the comic, it is also wrong. $\endgroup$
    – user126
    Commented Jul 21, 2010 at 1:02
  • 2
    $\begingroup$ but it is wrong nevertheless. $\endgroup$
    – mau
    Commented Jul 21, 2010 at 20:16
  • 2
    $\begingroup$ @mau: I still don't get the mistake? $\endgroup$
    – Casebash
    Commented Jul 21, 2010 at 21:01
  • 4
    $\begingroup$ 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. $\endgroup$ Commented Aug 4, 2010 at 17:19

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$

  • $\begingroup$ 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$. $\endgroup$
    – morgan
    Commented Aug 4, 2010 at 21:57
  • $\begingroup$ Why in the world was this edited now? A year after it was last touched? $\endgroup$
    – davidlowryduda
    Commented Aug 1, 2011 at 1:55
  • $\begingroup$ @mixedmath: One can only speculate! $\endgroup$ Commented Sep 17, 2011 at 15:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .