0
$\begingroup$

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


So I start with the base case, that is:

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


$\endgroup$
  • 2
    $\begingroup$ You should think of $p$ as a fixed prime. The induction is on the number of factors in the product $m_1\cdots m_k$. $\endgroup$ – carmichael561 Aug 25 '16 at 21:30
  • $\begingroup$ $k$ and $p$ do not have anything to do with eachother. $\endgroup$ – Arthur Aug 25 '16 at 21:35
  • 4
    $\begingroup$ Do you already know the theorem that prime $\,p\mid ab\,\Rightarrow\,p\mid a\,$ or $\,p\mid b?\ $ That is what yields the inductive step. $\endgroup$ – Bill Dubuque Aug 25 '16 at 21:36
  • $\begingroup$ Thanks for the pointers! I updated the post with another attempt using the theorem that @BillDubuque mentioned. How does it look now? $\endgroup$ – kojak Aug 25 '16 at 21:46
  • 2
    $\begingroup$ "If $p$ divides $m_1m_2...m_k$, that gives us $1/p$, meaning $p|1$ which supports the hypothesis." How could a prime number $p$ divide $1$? This is false. Maybe to understand better what is even neede dto be proved fix $p=7$. Now you need to show that for whatever integers $m_1, \dots ,m_k$ if $7$ divides their product then $7$ divides one of them. You do induction by the number of $m_i$ not the size of the $m_i$. $\endgroup$ – quid Aug 25 '16 at 21:53
-2
$\begingroup$

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

$\endgroup$

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.