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$

Question

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.

Answer 1

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.