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$


Base case: hold by Lemma $7.7.2$

Inductive step:

Assume that $$\bigvee_{i=1}^k p\mid a_i$$


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


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


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.

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

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


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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.