1. ## Prime proof

Euclid's Proof of Infinite Number of Primes: Suppose that $\displaystyle p_1=2 < p_2 = 3 < \dots < p_r$ are all of the primes. Let $\displaystyle P = p_1p_2...p_r+1$ and let $\displaystyle p$ be a prime dividing $\displaystyle P$; then $\displaystyle p$ can not be any of $\displaystyle p_1$, $\displaystyle p_2$, ..., $\displaystyle p_r$, otherwise $\displaystyle p$ would divide the difference $\displaystyle P-p_1p_2\dots p_r=1$, which is impossible. So this prime $\displaystyle p$ is still another prime, and $\displaystyle p_1, p_2, ..., p_r$ would not be all of the primes. $\displaystyle \square$

(a) Why can't $\displaystyle p$ divide $\displaystyle 1$, where $\displaystyle p$ is one of $\displaystyle \{p_{1}, p_{2}, p_{3}, \ldots, p_{r} \}$?

Proof: We want to show that $\displaystyle P \equiv P-1 (\mod p)$ is false. To prove this, choose $\displaystyle a,b \in \mathbb{Z}$ with $\displaystyle a \neq 0$. Then $\displaystyle a$ divides $\displaystyle b$ if there is an element $\displaystyle c \in \mathbb{Z}$ such that $\displaystyle b = ac$. Suppose for contradiction that $\displaystyle p$ divides $\displaystyle 1$. Then $\displaystyle 1 = pc$ where $\displaystyle c \in \mathbb{Z}$. Since $\displaystyle p > 1$ by definition, $\displaystyle c \not \in \mathbb{Z}$. Contradiction. Thus $\displaystyle p$ cannot divide $\displaystyle 1$. $\displaystyle \square$

Is this correct?

2. I think you're complicating things a bit. The only positive integer that can divide 1 is 1 which isn't a prime.

3. But in a rigorous sense the above proof is correct right?

4. you have to talk about $\displaystyle P$ whether it is a prime or not.

if $\displaystyle P$ is prime, then you are done is $\displaystyle P > p_i$ for all $\displaystyle i$.

if $\displaystyle P$ is not prime, then there is a $\displaystyle p \in \{p_1, p_2,...,p_r\}$ that divides $\displaystyle P$.

then $\displaystyle p|P - p_1p_2...p_r$ implies $\displaystyle p|1 \Longleftrightarrow p=1$. this is your contradiction since $\displaystyle p \in \{p_1, p_2,...,p_r\}$ and 1 is not in the set..