Discrete Math Problem about number theory

Let p be a prime number and a1, . .., a, integers. Prove the following Lemma by induction: Lemma. If p divides the product a1 . a2, ..., an, then p divides some a; for i E { 1, 2, ..., n}. Utilize the fact that the Lemma is true for n = 2 because of Lemma 9.4.2. Lemma 9.4.2 (if needed) Lemma 9.4.2. If p is a prime and p | ab, then p | a or p | b. Lemma 9.4.2 follows immediately from Unique Factorization: the primes in the product ab are exactly the primes from a and from b. But proving the lemma this way would be cheating: we're going to need this lemma to prove Unique Factoriza- tion, so it would be circular to assume it. Instead, we'll use the properties of god's and linear combinations to give an easy, noncircular way to prove Lemma 9.4.2. Proof. One case is if god(a, p) = p. Then the claim holds, because a is a multiple of p. Otherwise, god(a, p) # p. In this case god(a, p) must be 1, since 1 and p are the only positive divisors of p. Now god(a, p) is a linear combination of a and p, so we have 1 = sa + tp for some s, t. Then b = s(ab) + (tb)p, that is, b is a linear combination of ab and p. Since p divides both ab and p, it also divides their linear combination b