Lemma $7.2.2$ If a prime number divides the product of two natural numbers, then it divides at least one of the numbers.
Proof. $\dots$
Lemma $7.2.3$ For any natural number $n$, if a prime divides the product of $n$ natural numbers, then it divides at least one of the numbers.
Proof. This is a simple consequence of the previous lemma and mathematical induction. The previous lemma is the case $n=2$. Suppose that the result is true for $n$ factors, where $n$ is greater than or equal to $2$. Assume that $p$ is prime and that $p$ divides $a_1a_2\dots a_{n+1}$.If $p$ does not divide $a_1$, then by the case $n=2, p$ divides $a_2\dots,a_{n+1}$. Hence, by the inductive hypothesis, $p$ divides at least one of $a_2,\dots,a_{n+1}$.
(from UTM "A Readable Introduction to Real Mathmatics" Chapter $7$)
Here I tried to rewrite this proof of Lemma $7.2.3$
Proof.
Base case: hold by Lemma $7.7.2$
Inductive step:
Assume that $$\bigvee_{i=1}^k p\mid a_i$$
Show
$$\bigvee_{i=1}^{k+1} p\mid a_i$$
Combine base case and the assumption the following hold
$$\bigvee_{i=1}^k p\mid a_i\vee p\mid a_{k+1}$$
$$\Rightarrow \bigvee_{i=1}^{k+1} p\mid a_i\tag*{$\square$}$$
Here is an alternative proof using a loop
Lemma $7.2.3$
$$(\forall m(m\mid p)\rightarrow(m=1\vee m=p)\color{orange}{\text{ p is prime}}$$
$$\wedge p\mid a_1\dots a_n)$$
$$\rightarrow \bigvee_{i=1}^n p\mid a_i$$
Proof.
we can prove this use a loop
For each index $i\in[1,n-1]$:
By Lemma $7.2.2$
$$p\mid a_i\vee p\mid \prod_{j=i+1}^n a_j $$
$$\Rightarrow p\nmid a_i\rightarrow p\mid \prod_{j=i+1}^n a_j $$
Then $p\mid a_i\vee p\mid a_n$ where $i\in[1,n-1]$
$$\tag*{$\square$}$$
The first time I see proof by loop is in
$(1.6.6)$ Theorem. of "a course in linear algebra by david damiano"
Are they both valid proof $?$
Is proof by loop just another way to write mathematical induction, are they the same $?$
Thanks for your help.
Best Answer
It seems you are grasping at the general idea of n-ary extensions. The proof is a special case of the fact that we can similarly inductively extend any property $P$ that satisfies $\, P(ab) = P(a)\vee P(b)\,$ to products of any length (where $x \vee y := x\,$ or $\,y).\,$ Namely
$$\begin{align} P((a_1\cdots a_n) a_{n+1})\, &= \qquad\ \ \, \color{#c00}{P(a_1\cdots a_n)}\vee P(a_{n+1})\\[.3em] &=\, \color{#c00}{P(a_1)\vee \cdots P(a_n)}\vee P(a_{n+1})\ \ {\rm by}\ \ \color{#c00}{\rm induction} \end{align}$$
You have $\,P(a) := p\mid a.\,$ Associativity is the only property of multiplication and $\vee$ that is used, so the proof is really about $n$-ary extension of monoid homomorphisms.