If p is a prime and p divides a1 a2 an prove that p divides

If p is a prime and p divides a_1 a_2 ... a_n, prove that p divides a_i for some i.

Solution

Let us prove this using Mathematical induction.

Step-1:

When n=2, the given statement is true (By Euclid\'s lemma).

Step-2:

Let us assume that,

if p| a₁ a₂ a₃ ... a_k-1, p|a_i for some i<k-1.

Step -3: Let us prove this when n=k.

For n>2, we have

a₁ a₂ a₃ ... a_k = (a₁ a₂ a₃ ... a_k-1) a_k = product of two numbers

Let p|a₁ a₂ a₃ ... a_k

So again by Euclid\'s lemma,

p|a₁ a₂ a₃ ... a_k-1 (or) p|a_k

Here the second case is obvious. Let us consider the first case where p|a₁ a₂ a₃ ... a_k-1.

Then from step -2, p|a_i, for some i < k-1.

So, by Mathematical induction the given statement is true for all \'n\'. (where n is a natural number)