2
$\begingroup$

How can I prove that there are infinitely many primes without using contradiction?

I know the proof that is (not) by Euclid saying there are infinitely many primes. It assumes that there is a finite set of primes and then obtains one that is not in that set.

Say for some reason I want to prove it without using contradiction. Maybe I'm contradictaphobic. How could I go about doing this?

$\endgroup$
  • $\begingroup$ @Burak You are right. Post that as an answer please? $\endgroup$ – Joao Dec 6 '14 at 4:34
  • $\begingroup$ Since 'infinite set' is defined as not being finite, the usual proof is actually not by contradiction, but rather a simple introduction of the negation. $\endgroup$ – Git Gud Dec 6 '14 at 4:39
  • $\begingroup$ As people have hinted, just make it a proof by construction. In any case, your contradictophobia probably needs professional help :-) $\endgroup$ – Carl Witthoft Dec 6 '14 at 20:08
  • 2
    $\begingroup$ People are hating on the OP's contradictophobia as if it is an esoteric problem. Intuitionists, I assume, are so because of the same issue. It may not be something relevant for mathematical practice, but epistemologically there's something here. $\endgroup$ – Git Gud Dec 7 '14 at 11:46
  • $\begingroup$ @CarlWitthoft at least I don't have direct-proofophobia! $\endgroup$ – Joao Dec 7 '14 at 22:16
7
$\begingroup$

Actually, that proof can be phrased in a way to avoid contradiction. Let ${\cal P}=\{p_1,...,p_n\}$ be a non empty finite set of primes. Then let $a=1+\prod_{p\in\cal P}p$.

By the usual argument there must be a prime $p\mid a$, $p\notin\cal P$. This proves that any finite set of primes cannot include all primes and so there must be infinitely many.

EDIT: Given the almost-infinite sequence of comments, let me spell out the "usual argument":

  • $\emptyset\neq\cal P$ is a finite set of primes;
  • $a=1+\prod_{p\in\cal P}p$;
  • then $a\equiv1\bmod p$ for all $p\in\cal P$ and $a\neq\pm1$;
  • but: for all $a\in\Bbb Z\setminus\{\pm1\}$ there exists a prime $q$ such that $a\equiv0\bmod q$
  • $1\not\equiv0\bmod q$
  • therefore $q\notin\cal P$;
  • therefore there's no finite set containing all primes.

QED

$\endgroup$
  • 2
    $\begingroup$ Hmm. Don't you still use contradiction to argue that none of the $p\in\mathcal{P}$ divide $a$? $\endgroup$ – Cameron Williams Dec 6 '14 at 4:36
  • $\begingroup$ No. A prime in $\cal P\cap{\rm supp}(a)$ divides $1$, thus there are no such. Don't use contradiction! $\endgroup$ – Andrea Mori Dec 6 '14 at 4:39
  • $\begingroup$ A proof by contradiction assumes $\lnot P$, shows this leads to absurdity, and concludes $P$. There is nothing like this in Andrea Mori's argument. $\endgroup$ – MJD Dec 6 '14 at 4:40
  • 2
    $\begingroup$ How do you prove that $q\not \in \mathcal P$ 'directly'? $\endgroup$ – Git Gud Dec 6 '14 at 12:04
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – user642796 Dec 8 '14 at 12:21
6
$\begingroup$

The simplest direct proof I know is one which involves infinite series. One can show that $\sum\limits_{p\text{ prime}}\frac{1}{p}$ diverges. Particularly, it means that there cannot be finitely many primes since the sum of finitely many nonzero numbers is finite. (There is a very slight contradiction - or contrapositive - argument in here if you look closely enough.) That said, you should definitely combat your contradictaphobia... proofs by contradiction are everywhere in mathematics. Hamstringing yourself by not accepting or feeling at ease with such proofs will make mathematics quite challenging at times.

$\endgroup$
  • $\begingroup$ Not really... if I'm right OP's concern with proof by contradiction is that a proof by contradiction goes something like: Prove that the bottle of wine is in front of me. Step 1: Suppose you put your hands in front of your eyes. Step 2: Notice that the bottle disappeared . Step 3: Deduce that the bottle is in front of me. qed..... So what happens is that you don't believe the bottle is in in front of you when you see it but you believe that because not seeing it when you block your view and then seeing it when you don't proves that it is there. In a sense you assumed not not P to be true... $\endgroup$ – shooting-squirrel Dec 6 '14 at 5:08
  • 2
    $\begingroup$ @shooting-squirrel um... huh? :-P I'm sorry but I couldn't make any sense of that. (Though admittedly, I have a hard time imagining any objection to proof by contradiction that would admit a sensible explanation, so don't take that as a judgment on your ability to explain things.) $\endgroup$ – David Z Dec 6 '14 at 6:16
5
$\begingroup$

In the proof that is attributed to Euclid, what you are really doing is this: For any integer $n \geq 1$ you are producing a number, namely one plus the product of all primes less than or equal to $n$, whose prime factors have to be greater than the biggest prime less than $n$.

Therefore, given the fundamental theorem of arithmetic, Euclid's proof can be modified in such a way that it actually proves that for any integer $n \geq 1$ there exists a prime $p \geq n$, that is, there are arbitrarily large primes.

$\endgroup$
  • 2
    $\begingroup$ For instance $n!+1$ must be divisible by a prime bigger than $n$ $\endgroup$ – Andrea Mori Dec 6 '14 at 4:42
4
$\begingroup$

Let $F_n=2^{2^n}+1$ be the sequence of Fermat numbers. It is relatively easy to show that, for distinct $i,j$ we have $\gcd(F_i,F_j)=1$. Therefore, if we let $p_n$ be a sequence of primes such that $p_n$ divides $F_n$ (which is possible, since every number has at least one prime divisor), then each $p_n$ is distinct (since $p_n>1=\gcd(F_i,F_j)$), and there are infinitely many of them.

$\endgroup$
  • 1
    $\begingroup$ Ah, beat me to it... $\endgroup$ – abiessu Dec 6 '14 at 4:51
4
$\begingroup$

Here is a proof that uses a bit of group theory.

We show that, if $p$ is prime, then $2^p-1$ is divisible by a prime $q \gt p$.

Suppose that $q$ divides $2^p - 1$. Consider the multipicative group $\mathbb Z_q \setminus \{0\}$. Since $q$ divides $2^p-1$, the element $2$ has order $p$ in $\mathbb Z_q \setminus \{0\}$. Since this group has order $q-1$, by Lagrange's Theorem we have $p$ divides $q-1$. Therefore $p \lt q$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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