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$ – linear_combinatori_probabi 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

  • $\begingroup$ This can't be correct. You aren't using the fact that p is a prime anywhere in this proof. What if there is a factor of b and a factor of k that produce a value that is divisible by p but separately they are both not divisible. For example: 6 does not divide 2 and 3 but it divides 2 * 3. $\endgroup$ – Mitesh Kumar Dec 17 '19 at 17:49

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.