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!
Best Answer
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$