Prove that if $p \mid a_1a_2 \ldots a_n$, then $p \mid a_j$ for some $j$ with $1 \le j \le n$

Let $p$ be a prime number and $a_1, a_2, \ldots, a_n$ be integers. Prove that if $p \mid a_1a_2 \ldots a_n$, then $p \mid a_j$ for some $j$ with $1 \leq j \leq n$.

The hint was to use induction.

So for the base case ($n = 1$):

$p \mid a_1$ would imply $p \mid a_j$ for some $j$ with $1 \leq j \leq 1$, so $j$ would have to equal 1, which would say that $p \mid a_1$ which was assumed so the base case holds.

For the induction step:

I would assume that if $p \mid a_1a_2 \ldots a_k$ then it is true that $p \mid a_j$ for some $j$ with $1 \leq j \leq k$, and would have to prove that $p \mid a_1a_2 \ldots a_k \cdot a_{k + 1}$ implies that $p \mid a_j$ for some $j$ with $1 \leq j \leq k + 1$.

This is where I get stuck, I think you only have to check the case where $j = k + 1$ because if $j$ was $a_1$ through $a_k$ the initial condition would hold? But I'm not sure.

• That's pretty much exactly right; you're not really stuck, you actually have the proof method; the k+1 case splits into the new case and the existing known case from the induction assumption. – Joffan Apr 23 '15 at 1:38
• Again, as in your prior related question, it would help to know what results you have available.Do you know that prime $\,p\mid ab\,\Rightarrow\,p\mid a\,$ or $\,p\mid b$? That's the key property behind the induction. – Bill Dubuque Apr 23 '15 at 1:47

The base case is when $n=2$ and it is called Euclid's lemma.
To see how you can prove the result via induction we shall do it over $n$ (The number of factors).
Suppose that you have proved it for $n$ factors and wish to prove it for $n+1$. We must prove that if $p|a_1a_2\dots a_{n+1}$ then $p$ divides one of the $a_j$'s. Notice that $p|(a_1a_2\dots a_{n})a_{n+1}$ so by the base case $p|a_1a_2\dots a_{n}$ or $p|a_{n+1}$.
If $p|a_{n+1}$ we are done, on the other hand if $p|a_1a_2\dots a_{n}$ then by the inductive step $p|a_j$ for some $1\leq j\leq n$ so we are also done.