Page 96 - 'Blast_Into_Math

Blast into Math! Prime nummers: indestructimle muilding mlocks

The following proposition and its corollary are the last ingredients we need to prove the FTA. The
chocolate chips are usually the last ingredient one mixes into the dough to make chocolate chip cookies.

Proposition 5.1.4 (Chocolate Chip Proposition (CCP)). Let S be a finite sequence of k non-zero integers
for some k ∈ N . If p is prime, and p divides the product of all the elements of S, then p divides at least
one of the elements in S .

Proof: We don’t know how many integers are in the finite sequence S , but we do know that there is
at least one integer in S , because S has k elements, and k ∈ N . S is like a bag of chocolate chips,
and we don’t know exactly how many are inside. If S contains just one element, (one chocolate chip)
let’s call it c , (for chocolate chip), then S = {c} . The proposition says that if the prime p divides the
product of all the elements of S , then p divides at least one of the elements of the set. In this case, the

product of all the elements of S is c . So, if p|c , it’s certainly true that p divides one of the elements
of the S , because S = {c} . So, we have now proven that the proposition is true if the set has one
element. We want to prove that the proposition is true if the set has k elements, for each k ∈ N . Since
we have already proven it is true for k =1, we can finish the proof of the proposition using induction.

We have already proven the base case. The next step is to assume the proposition is true if the finite
sequence has k elements for some k ≥ 1. We need to show that the proposition is also true if the set
has k +1 elements. Assume S is a finite sequence of k +1 non-zero integers, and p is a prime such
that p divides the product of all the elements of S. It is convenient to write

S = {c 1 ,c 2 ,...,c k+1 }.

So, c 1 is the first element of the finite sequence, c 2 is the second, and all the way up to the last c k+1 .
To prove the proposition, we need to show that if

p|(c 1 ∗ c 2 ∗ ... ∗ c k ∗ c k+1 ),

then p divides at least one element in S . Let’s think about the first element in S . By the Shortbread

Proposition, either (c 1 ,p)= 1 or (c 1 ,p)= p , and p|c 1 . If p|c 1 , we’re done, because c 1 ∈ S , and so
p divides at least one of the elements in S (namely, c 1 ). Otherwise, we know that

p|c 1 ∗ (c 2 ∗ ... ∗ c k ∗ c k+1 )and (p, c 1 )= 1.

By the Ingredient Proposition with (c 2 ∗ ... ∗ c k ∗ c k+1 ) playing the role of b , p playing the role of
n , and c 1 playing the role of a ,

p|(c 2 ∗ ... ∗ c k ∗ c k+1 ).

96