# 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$

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.

• "Is proof by loop just another way to write mathematical induction, are they the same" They seem to be the same to me. – fleablood Oct 14 '19 at 0:57

## 2 Answers

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.

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.

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.

• Note that your Lemma 7.2.2 is actually saying all irreducibles in $\mathbb{Z}$ are prime. – justadzr Oct 14 '19 at 1:13