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

Related videos on Youtube

kojak
Author by

kojak

Updated on August 01, 2022

Comments

  • kojak
    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


    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.


    • carmichael561
      carmichael561 about 7 years
      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$.
    • Arthur
      Arthur about 7 years
      $k$ and $p$ do not have anything to do with eachother.
    • Bill Dubuque
      Bill Dubuque about 7 years
      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.
    • kojak
      kojak about 7 years
      Thanks for the pointers! I updated the post with another attempt using the theorem that @BillDubuque mentioned. How does it look now?
    • quid
      quid about 7 years
      "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$.
    • Henrik supports the community
      Henrik supports the community about 7 years
      Why didn't you remove the first attempt? Nobody is going to gain anything from that. It looks totally in-comprehensible to me. What do you mean by "that gives us $1/p$" $1/p$ is a constant, not something you can get.
    • Jyrki Lahtonen
      Jyrki Lahtonen about 7 years
      The base case has $k=1$. When $k=1$ the product $m_1m_2\cdots m_k=m_1$. So the claim in the base case reads: If $p\mid m_1$ then $p$ divides one of the numbers $m_1$. When $k=2$ the claim reads: If $p\mid m_1m_2$ then $p$ divides one of the numbers $m_1,m_2$.