Question on a proof that there are infinitely many primes

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 mathbbN$. Then, form the product
beginalign*
N = mathopPilimits_i=1^m p_i + 1.
endalign*
From here there are several ways to proceed. But, this is where I find myself getting confused.

Since $mathbbZ$ is closed under multiplication and addition, $N in mathbbZ$, 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 mathbbZ, 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 $frac1p_i in mathbbZ$, 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 $frac1p_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.

1 Answer
1

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=prodlimits_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=acdot p_j$.

That is, $acdot p_j = p_1cdot p_2cdots p_jcdots p_m + 1$

Now, by subtracting and factoring, we have $1 = p_jcdot(a - p_1cdot p_2cdots p_j-1cdot p_j+1cdots p_m)$

Note, however, that $(a-p_1cdots 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).

Required, but never shown

Required, but never shown

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.