Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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. –  Justin L. Jul 21 '10 at 0:12
6  
I think that some effort should be necessary on the part of the person asking the question... –  user126 Jul 21 '10 at 0:18
9  
+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 :) –  e.James Jul 21 '10 at 0:40
3  
Mathunderflow should be like mathoverflow for lower level problems. –  user126 Jul 21 '10 at 0:44
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. –  Justin L. Jul 22 '10 at 2:03

9 Answers 9

up vote 38 down vote accepted

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.

share|improve this answer
2  
The proof also works in the ring of polynomials over a finite field. –  Akhil Mathew Jul 21 '10 at 0:29
1  
Quantity is better than quality, my answer is better. :D –  BBischof Jul 21 '10 at 3:21
6  
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 –  Bill Dubuque Jul 29 '10 at 1:14
9  
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.) –  ShreevatsaR Aug 4 '10 at 17:23
1  
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 –  Bill Dubuque Aug 5 '10 at 13:53

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 $\ $ Since $\rm N+1 > 1\:$ it has a prime factor $\rm P\:.\ $ $\rm P$ can't divide $\rm N$ since $\rm N$ is coprime to $\rm N+1\ $ (viz. if $\rm\: P$ divides $\rm N+1\:$ and $\rm N$ then $\rm P$ divides their difference $\rm N+1 - N = 1\:,\: $ a contradiction). 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)\: $ produces 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.

share|improve this answer
    
I have not seen this, it is as you say the essence of the Euclid proof. Also, a good exercise for fresh students. –  AD. Sep 25 '10 at 19:01
    
@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? –  Bill Dubuque Sep 25 '10 at 19:05

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

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

share|improve this answer
    
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 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. –  Pete L. Clark Aug 11 '10 at 14:37
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. –  BBischof Aug 11 '10 at 16:08
    
@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. –  Pete L. Clark Aug 11 '10 at 20:25
    
@PLC np, I just haven't thought about it yet. –  BBischof Aug 11 '10 at 20:33
6  
I heard back from Steven Sam. He agrees with me and will make appropriate modifications. –  Pete L. Clark Aug 11 '10 at 21:54

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


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

share|improve this answer

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.

share|improve this answer
1  
However, proving transcendence of $\pi$ most probably requires proving infinitude of primes. See mathoverflow.net/questions/21367 –  sdcvvc Jan 23 '12 at 18:26

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

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

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: http://math.stackexchange.com/questions/3243/does-92n-1-always-have-a-prime-factor-larger-than-40/

share|improve this answer
4  
So not only are there infinitely many primes, there are infinitely many primes > 40? :-) –  Steven Stadnicki Oct 15 '10 at 22:05
6  
@Steve: Yes, as they say, when you are over 40, you are past your prime :-) –  Aryabhata Oct 15 '10 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.

share|improve this answer
    
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? –  Srivatsan Aug 1 '11 at 2:08

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$

share|improve this answer
    
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$. –  alexx Aug 4 '10 at 21:57
    
Why in the world was this edited now? A year after it was last touched? –  mixedmath Aug 1 '11 at 1:55
    
@mixedmath: One can only speculate! –  The Chaz 2.0 Sep 17 '11 at 15:06

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.