From $n=2$ to $n$-ary Euclid lemma $\ p\mid a_1\cdots a_n\Rightarrow\ p\mid a_1\,$ or $\,\cdots\, p\mid a_n$

How to prove a generalized Euclid lemma par induction after proving Euclid lemma?
I want to prove the generalized lemma, to prove by rearranging the product of number and use Euclid lemma as a model. A proof will be nicer if it can use induction principle.

Solution 1:

The induction almost writes itself: it is just a matter of writing down your informal reasoning in the language of induction.

We want to prove that for every integer $n\ge 2$, if the prime $p$ divides the product $a_1a_2\cdots a_n$, then $p$ divides at least one of the $a_i$. The result has been already proved for $n=2$. It remains to do the induction step.

Suppose the result is true when $n=k$. We show the result is true when $n=k+1$.

So we are told that $p$ divides $a_1a_2\cdots a_ka_{k+1}$. Thus $p$ divides $(a_1a_2\cdots a_k)a_{k+1}$. This is a product of two numbers. Thus $p$ divides $a_1a_2\cdots a_k$ or $p$ divides $a_{k+1}$.

If $p$ divides $a_{k+1}$ we are finished. If $p$ does not divide $a_{k+1}$, then $p$ divides $a_1a_2\cdots a_k$. Then by the induction hypothesis $p$ divides one of the $a_i$ ($1\le i\le k$), and we are finished.

Solution 2:

Hint $\ $ The inductive step is: $\rm\:p\:|\:a_{n+1}(a_n\cdots a_1)\:\Rightarrow\:p\:|\:a_{n+1}\ \ or\ \ p\:|\:a_n\cdots a_1\:$ by the prime divisor property, therefore, by induction $\rm\:p\:|\:a_n\cdots a_1\:\Rightarrow\: p\:|\:a_n\ \ or\ \ \cdots\ \ or\ \ p\:|\:a_1.$

More algebraically we could prove contrapositive: $\rm\: mod\ p\!:\ $ $\rm\:x,y\ne 0\:\Rightarrow\:xy\ne 0\:$ inductively extends to: a product of nonzero elements is nonzero. Here is a proof the two-element base case.

Remark $\ $ The proof method works quite generally: if $\rm\:xy\in S\:\Rightarrow\: x\in S\ or\ y\in S\:$ then, by induction, $\rm\:x_1\cdots x_n\in S\:\Rightarrow\: x_1\in S\,\ or\,\cdots\, or\,\ x_n\in S\ \ $ (above $\rm\:S = p\,\Bbb Z).$ If we view the product as a binary tree expression, then the inductive proof essentially lifts the property "$\in S$" up from the root to the leaves.