Euclid's Proof of Infinite Number of Primes: Suppose that are all of the primes. Let and let be a prime dividing ; then can not be any of , , ..., , otherwise would divide the difference , which is impossible. So this prime is still another prime, and would not be all of the primes.

(a) Why can't divide , where is one of ?

Proof: We want to show that is false. To prove this, choose with . Then divides if there is an element such that . Suppose for contradiction that divides . Then where . Since by definition, . Contradiction. Thus cannot divide .

Is this correct?