4

I need some help understanding a given proof so that I can in turn prove something. In a question I am given that:

In order to prove that there is no "largest" prime number, for any prime $p$ just show there is a new prime $q$ such that $q>p$. Write $$N=(2\cdot3\cdot5\cdot...\cdot p)+1,$$ and if $N$ is prime we are done, otherwise $N$ is divisible by some prime $q$.

I am told to prove $q>p$. I think I can figure out how to do this, but there is one thing I don't understand in the above box. I understand how the proof is done when $N$ is prime, but I don't understand why "$N$ is divisible by some prime $q$" otherwise.

May somebody please help me understand why this is true. Thanks in advance!

user66807
  • 1,313
  • 1
    I mentioned it below, but in order to hit all the natural numbers, we need our arbitrary $N$ representation to include powers of primes as well too, so $N=(2^{k_1}\cdot{3}^{k_2}\cdot...\cdot{p}^{k_n})+1$ and ${2,3,5,...,p}$ is our set of finite primes. – Eleven-Eleven Sep 19 '13 at 03:26
  • @ChristopherErnst yes I saw you mention that below and I understand why we need $N$ to be written that way. Thanks. – user66807 Sep 19 '13 at 03:29
  • does my example help to clarify your understanding? – Eleven-Eleven Sep 19 '13 at 03:32
  • @ChristopherErnst yes it certainly does help me understand why $N$ must be divisible by some other prime $q$. Now I can also see why $q>p$. – user66807 Sep 19 '13 at 03:36
  • 3
    It is not relevant whether $N$ is prime or not. Every number $n\gt 1$ is divisible by some prime. If the number is a prime, like $n=17$, then $n$ is divisible by $17$, for $17=17\cdot 1$. So there always exists a prime $q$ such that $q$ divides $N$. We can now argue that $q$ cannot be any of $2,3,5,\dots,p$, since when we divide $N$ by any of these, we get a remainder of $1$. So any prime divisor $q$ of $N$ must be greater than $p$. This is because in forming $N$ we have used all the primes $\le p$. – André Nicolas Sep 19 '13 at 03:56

2 Answers2

3

Assume the primes are finite. So $N=(2^{k_1}⋅3^{k_2}⋅...⋅p^{k_n})+1$. But since there are finitely many, $N$ should also be written as a product of our finite number of primes (since it is NOT in its present form). Now, what happens then you try to do this? I.E., can you divide N by 2? how about 3? How about $p$?....

Hint:
$$N=2(2^{k_1-1}3^{k_2}5^{k_3}...p^{k_n})+1 \text{ so } 2\text{ does not divide }N$$ $$N=3(2^{k_1}3^{k_2-1}5^{k_3}...p^{k_n})+1 \text{ so } 3\text{ does not divide }N$$ $$...$$ $$N=p(2^{k_1}3^{k_2}5^{k_3}...p^{k_n-1})+1 \text{ so } p\text{ does not divide }N$$ Turns out you can not divide $N$ by any of our primes given, but $N$ $must$ be written as a product of primes, then there must exist a prime $q$ that divides $N$, and I think it's easy to see that this prime is greater than $p$

Eleven-Eleven
  • 8,806
  • 2
    This really doesn't make sense. "So $N=\dots$"? And to arrive at the contradiction to having a complete list, there's no need to produce any more than one additional prime not on our list. So there's no need to confuse matters with all those exponents. – Ted Shifrin Sep 19 '13 at 04:01
  • 1
    I see what your saying. It's not about the totality of the natural numbers but about the contradition to the idea the primes are finite. Thank you for clarifying. – Eleven-Eleven Sep 19 '13 at 04:04
1

$\textit{Every}$ integer is divisible by some prime, so if $N$ is not itself prime, then $N$ is divisible by some prime $q<N$.

You know that $q$ is greater than $p$ because $N$ is one more than a multiple of any prime less than or equal to $p$ (you can probably make this a little more formal, but that's the basic idea).

William Ballinger
  • 3,682
  • 1
    I understand what you are saying until you say "than a multiple of any prime less that $p$" because isn't $N$ one more than a multiple of any prime less than and including $p$? The concept you are conveying is clear, I just want a little clarification on that bit you said. – user66807 Sep 19 '13 at 03:06
  • 3
    in your problem you have $N$ as $N=(2\cdot{3}\cdot{5}\cdot...\cdot{p})+1$, but in reality each prime has a power associated with it so to be completely rigorous, $N=(2^{k_1}3^{k_2}5^{k_3}...p^{k_n})+1$. – Eleven-Eleven Sep 19 '13 at 03:14