Suppose a prime number $p$ divides the product $a_1 a_2 ... a_n \in \mathbb{Z} $ then $p$ divides at least one of the factors of $a_i$

Question

I know i need to use induction but i really have no concept on how to go about it.

Base case: Let $p$ divide $a_1$ then p will be a factor of $a_1$???

Inductive step: No idea how to phrase this.

Answer 1

Let's divide the problem into parts. First, you should know this very well known result which turns out to be extremely uselful for these 'elementary number theory' problems:

Lemma. Let $d, a, b \in \mathbb{Z}$. If $d | ab$ and $d$ is coprime with $a$, then $d | b$.

Proof. Recall that by Bezout's identity, if $d$ and $a$ are coprime, there exist $s,t \in \mathbb{Z}$ such that $ds+at = 1$. Now, multiplying by $b$ we get that

$$ dbs + abt = b. $$

Since $d | dbs $ and $d | abt$ because $d$ divides $ab$, we have that $d | dbs + abt = b$ as claimed. $\square$

Now, in particular this gives a useful tool for divisibility in the case of primes,

Proposition. Let $p,a,b \in \mathbb{Z}$ with $p$ prime. Then either $p | a$ or $p | b$.

Proof. Suppose that $p \not | a$. Note that this is the same as $p$ being coprime with $a$: the only factors they can have in common are $p$ and $1$, and the former is discarded precisely because $p \not | a$. Thus, by the previous lemma, this implies $p | b$. $\square$

Observe that the previous proposition is in fact the base case of your problem, when $n = 2$. Now, to conclude, let's prove the original question by induction: suppose that $p | a_1 \cdots a_n$ implies $p | a_i$ for some $1 \leq i \leq n$, for any $a_1, \dots, a_n \in \mathbb{Z}$ and let's see that the same holds for $n+1$. Let $a_1 , \dots a_{n+1}$ be integers such that $p | a_1 \cdots a_{n+1}$. Now, write

$$ b := a_2 \cdots a_{n+1}. $$

In this new terms, we have that $p | a_1b$. If $p | a_1$, we are done. Otherwise, by the previous proposition, necessarily $p | b = a_2 \cdots a_{n+1}$. Since this is a product of $n$ integers, by inductive hypothesis there exists $1 \leq i \leq n+1$ such that $p | a_i$. In any case, $p$ divides some factor. $\square$