7
$\begingroup$

There are several ways to prove this fact, and I can think of two reasonably clear ways, but my professor presented a sketch of a proof that I can't quite follow. I'm going to replicate his logic as best as I can.

Theorem. There are infinitely many primes.

Proof. Assume for a contradiction that there are only finitely many primes, which we can list as $p_1, p_2, p_3, \ldots, p_m$ for some $m \in \mathbb{N}$. Then, form the product \begin{align*} N = \mathop{\Pi}\limits_{i=1}^m p_i + 1. \end{align*} From here there are several ways to proceed. But, this is where I find myself getting confused.

Since $\mathbb{Z}$ is closed under multiplication and addition, $N \in \mathbb{Z}$, and since $N > p_i, \forall i$, $N$ is not a prime. So, there exists some $p_i$ such that $p_i \mid N$, so $\exists a \in \mathbb{Z}, a \cdot p_i = N$, i.e., $a \cdot p_i = p_1 \cdot p_2 \cdot p_3 \cdots p_m + 1$.

From here, my professor concluded that $\frac{1}{p_i} \in \mathbb{Z}$, an absurdity and thus a contradiction. I can't quite figure out how to get there. If we divide both sides through by $p_i$, since $1 \leq i \leq m$, we get $a$ on the LHS and two terms on the RHS, one of which is a product of $m - 1$ primes (after cancelling) and one of which is $\frac{1}{p_i}$. From here, perhaps we could subtract the product of $m - 1$ terms, clearly an integer by closure under multiplication, from $a$, also an integer. Then, by closure under subtraction, $a$ less this product is also an integer, in which case we've found our contradiction.

Is this correct?

Thanks in advance.

$\endgroup$
  • 2
    $\begingroup$ Yes, that's correct. $\endgroup$ – quid Aug 30 '18 at 0:51
  • 1
    $\begingroup$ Excellent. Thank you. $\endgroup$ – Matt.P Aug 30 '18 at 0:54
13
$\begingroup$

I disagree with the use of "division" in any proof for elementary number theory. The concept of division is usually only formally introduced much later in a course from where you appear to be at the moment.

So, we get to letting $N=\prod\limits_{i=1}^mp_i + 1$ and we determined that $N>p_i$ for all $i$ and so $N$ is not one of the elements in our list of primes. Ergo, $N$ must be composite (by theorem proved earlier, every natural number is either 0, 1, prime, or composite). That is, there is some naturals $j$ and $a$ such that $N=a\cdot p_j$.

That is, $a\cdot p_j = p_1\cdot p_2\cdots p_j\cdots p_m + 1$

Now, by subtracting and factoring, we have $1 = p_j\cdot(a - p_1\cdot p_2\cdots p_{j-1}\cdot p_{j+1}\cdots p_m)$

Note, however, that $(a-p_1\cdots p_m)$ is an integer and so too is $p_j$. Notice that this would then imply that $p_j$ is a divisor of $1$, but $1$ has no divisors except itself. This is our contradiction.

Note, the above argument completely bypassed the need for referring to division, though it does make use of divisibility (something which is perfectly acceptable to refer to and use in these level of proofs).

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