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

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.

• 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. – Jyrki Lahtonen Nov 13 '13 at 7:44
• Anyone knows how to prove the case when $p$ is not prime? – 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