Suppose than $n$ is a natural number, and that $a_1, a_2, \ldots, a_n$ are integers. Let $p$ be a prime. If $p\mid(a_1a_2 \cdots a_n)$ then there exists an $i$ with $1 \leq i \leq n$ such that $p\mid a_i$.

I want to prove this with the Principle of Mathematical Induction. For my base case I will let $n = 1$. I also want to possibly use Euclid's Lemma.

I'm not entirely sure where to go from here.

  • 1
    $\begingroup$ Usually the case $n=2$ has been covered in class: $p\mid ab$ implies $\ldots$. Please locate that from your lecture notes or textbook and include. That's actually helpful for the induction also. $\endgroup$ – Jyrki Lahtonen Nov 13 '13 at 7:44
  • $\begingroup$ Anyone knows how to prove the case when $p$ is not prime? $\endgroup$ – Ning Wang Mar 18 '18 at 0:16

For the case $n = 1$, clearly you're done, since if $p \mid a_1$, then $p \mid a_1$.

Assume that it's true for $n = k - 1$. Then for the case $n = k$ we have $a_1 \dots a_k = (a_1 \dots a_{k-1})a_k = b a_k$. If $p \mid a_k$ we're done otherwise $p \mid b$ and since we've proved it for all $n = k-1$, we have that $p$ must then divide one of $a_i, i = 1 \dots k-1$. QED


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.