33
$\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?

  • 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

44

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.

  • 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
41

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 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.

  • 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

  • 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

  • 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$?

  • 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 conce$p$tual 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
    @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]