# A homework problem in number theory regarding prime numbers

## Problem:

Suppose $p$ is a prime number such that $p | a_1a_2...a_n$ where $a_i \in \mathbb{Z}$. Then, $p$ divides at least one $a_i$

## Try:

We first prove it for $n=2$. i.e. assuming $p | a_1a_2$. If $p$ does not divide $a_1$, then we can find integers $r,s$ so that $a_1 r + p s = 1$ which implies $a_2 a_1 r + a_2 p s = a_2$. By hypothesis, there is some $t \in \mathbb{Z}$ so that $pt = a_1 a_2$. Hence, we have $ptr + a_2 p s = a_2 \implies p(tr+a_2 p) = a_2 \implies p | a_2$.

Now, assume that if $p | a_1 a_2 .... a_{n-1}$, then $p$ divides at least one $a_i$. Now, suppose $p | a_1a_2 ... a_n = (a_1...a_{n-1})a_n$ By the first paragraph, $p$ divides $a_1...a_{n-1}$ or $p$ divides $a_n$. But, using the induction hypothesis, we must have that $p$ divides at least one $a_i$. The result follows.

Is this proof sufficient? Do I need to be more explicit on certain parts?

• It looks just fine to me. – DonAntonio Feb 29 '16 at 8:16
• Maybe just add a sentence that makes it clear that you only use induction if $p$ divides $a_1\cdots a_{n-1}$, but that's nitpicking. The proof is good as it is. – 5xum Feb 29 '16 at 8:26
• Nitpicking again (in the context of a good proof): If $p$ does not divide $a_1$, then it must be relatively prime to $a_1$, and therefore we can find integers $r,s$ so that $a_1r+ps=1$. – Greg Martin Feb 29 '16 at 8:29

Assume by contradiction that $p$ doesn't divide any of $a_i$, so is relatively prime to all the $a_i$s. According to Euclid's Lemma (https://en.wikipedia.org/wiki/Euclid%27s_lemma) it turns out that $$\gcd(p,a_2a_3\cdots a_n)=1$$therefore $p|a_1$ which is a contradiction since $\gcd(p,a_1)=1$. Therefore $p$ divides at least one of the $a_i$s