# Proof by induction with a prime number

1,217

Base Case: m\$_1\$...m\$_k\$ is m\$_1\$. The hypothesis implies that p thus divides m\$_1\$. Thus, p divides at least one of the integers of the product m\$_1\$.

Recursive Step: Suppose that for at least one m\$_k\$, p divides m\$_1\$...m\$_n\$. By Bill Dubuque's hint, p divides m\$_1\$...m\$_n\$m\$_j\$ where j = (n + 1) implies that p divides m\$_1\$...m\$_n\$ or m\$_j\$. If it divides m\$_1\$...m\$_n\$, then by assumption for at least one m\$_k\$ it divides m\$_1\$...m\$_n\$. If it divides m\$_j\$, then for at least one m\$_k\$ it divides m\$_j\$. Thus, in either case for at least one m\$_k\$, p divides m\$_1\$...m\$_n\$m\$_j\$. Therefore, if for at least one m\$_k\$, p divides m\$_1\$...m\$_n\$, then for at least one m\$_k\$, p divides m\$_1\$...m\$_n\$m\$_j\$.

Share:
1,217

Author by

### kojak

Updated on August 01, 2022

• kojak over 1 year

I'm having trouble wrapping my head around proofs by induction with this problem:

Prove by careful induction on \$k\$ that, if \$p\$ is a prime number dividing the product \$m_1m_2...m_k\$ of (ordinary) integers \$m_1,...,m_k\$ where \$k\geqslant1\$, then \$p\$ divides at least one of the integers \$m_i, i =1,...,k.\$

Trying again based on feedback

\$k = 1\$

If \$p\$ divides \$m_1m_2...m_k\$, that gives us \$1/p\$, meaning \$p|1\$ which supports the hypothesis.

So the base case holds.

Now for the Inductive step, we have \$k +1\$ which would equate to \$2\$

Then we have \$m_1m_2...m_k = 1*2\$ and then \$1*2/p\$.

Since \$p∣ab \implies p∣a\$ or \$p∣b\$, we know that \$p|1\$ or \$p|2\$.

So the inductive step holds, and so does the hypothesis.