Prime proof

**particlejohn** · September 5th 2008, 07:32 PM

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?

**o_O** · September 5th 2008, 07:39 PM

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

**particlejohn** · September 5th 2008, 07:42 PM

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

**kalagota** · September 5th 2008, 08:03 PM

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..

Thread: Prime proof

LinkBack

Thread Tools

Display

Prime proof

Similar Math Help Forum Discussions

Relatively Prime Proof

Prime # Proof

Prime proof

Prime Proof

Prime Proof

Search Tags