# Thread: Prime proof

1. ## Prime proof

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

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

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

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

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

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