Alternative proof using a loop to prove that If $p$ is prime, and $p\mid a_1\dots a_n$, then p divides at least one in $a_1,\dots,a_n$

Question

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.

Answer 1

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.

Answer 2

The correct word for this kind of proof is induction. It is a valid proof but its logic may seem weak, so you may consider a stronger proof using Well Ordering Principle (though you can prove induction using WOP).

The definition of a prime (not an irreducible) is: if $p$ suffices $$p|ab\implies p|a\text{ or }p|b$$ Then $p$ prime. Supposedly, by contradiction, $\exists S$: $$S=\left\{n\in\mathbb{Z}^+\mid p\text{ prime},p|a_1a_2\cdots a_n,p\nmid a_i\forall i\right\}$$ By WOP, $\exists$ a least element $l\in S$ s.t. $l\leqslant k,\forall k\in S$. We can see that $1,2\notin S$, so $l\geqslant3$ and $l-1>0\notin S$. Since $l-1\notin S$, $p|a_1\cdots a_{l-1}\implies p|a_i$ for some $0<i<l$.

Since $2\notin S$, if $p|(a_1\cdots a_l)$, $p|(a_1\cdots a_{l-1})$ or $p|a_l$, and then we could see $$p|a_i\text{ for some }i\leqslant l$$ which proves that $l\notin S$ or $S=\emptyset$.

Q.E.D.