1
$\begingroup$

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.

$\endgroup$
2
  • 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$ Commented Nov 13, 2013 at 7:44
  • $\begingroup$ Anyone knows how to prove the case when $p$ is not prime? $\endgroup$ Commented Mar 18, 2018 at 0:16

1 Answer 1

2
$\begingroup$

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

$\endgroup$
1
  • $\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$ Commented Dec 17, 2019 at 17:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .