# Proof regarding prime numbers:

THEOREM:

If a prime $p$ divides a product $a_1 \cdot \cdot \cdot a_n$, then $p$ divides at least one of its factors, $a_i$.

This is my attempt at the proof, the book I am reading from suggests using induction on the number of factors, but I went a different direction because I couldn't get anywhere with induction:

Suppose $p\mid a_1\cdot\cdot\cdot a_n$ and $p\nmid a_i^*$ where $a_i^* = \dfrac{a_1\cdot\cdot\cdot a_n}{a_i}$ and $a_i$ is one of the factors of the product.

We know that, \begin{align*} \gcd(p,a_i^*) = 1\\ a_i = \gcd(a_ip,a_ia_i^*) \end{align*}

And since $p\mid a_ip,a_1\cdot\cdot\cdot a_n \Longrightarrow p\mid(a_ip,a_1\cdot\cdot\cdot a_n) \Longrightarrow p\mid a_i$.

Has the theorem been proven?

• There is a bit of trouble with the part $p\nmid a_i^*$. Are you sure such an $i$ always exists? What happens if it doesn't? – EuYu May 8 '13 at 4:58
• What's your definition of "prime"? In number theory it is often defined as an element such that $p\mid ab$ implies $p\mid a$ or $p\mid b$ (possibly both). Thus, if you suppose that $p\mid a_1\cdots a_{n-1}$ always implies $p\mid a_i$ for some $1\le i<n$, and we know that $p\mid a_1\cdots a_n$ implies $p\mid a_1\cdots a_{n-1}$ or $p\mid a_n$... – anon May 8 '13 at 5:12
• @EuYu if such an $i$ doesn't exist then the theorem is proven because that implies there exists at at least one of the factors of the product that is divisible by $p$. – kvmu May 8 '13 at 6:00
• @kvmu Are you counting $a_i^*$ as the factor? The question seems to be asking to prove that $p$ divides one of the $a_i$s. How exactly would you fill in your details? – EuYu May 8 '13 at 6:06
• @EuYu $a_i^*$ is the product $a_1\cdot\cdot\cdot a_n$ except without a factor of $a_i$ – kvmu May 8 '13 at 6:09

I got confused by your argument. The induction follows easily from the following result.

Claim: If $p$ divides $ab$ then $p$ divides $a$ or $p$ divides $b$ (or both).

Because $p$ is prime, its only divisors are $1$ and $p$. This means $\gcd(a,p)$ must be either $p$ or $1$. If $\gcd(a,p) = p$, then $p$ divides $a$ and we're done.

Otherwise $\gcd(a,p) = 1$. Then using Euclid's algorithm you get

$$ra + sp = 1$$

for integers $r$ and $s$. Multiplying both sides by $b$ you get

$$rab + spb = b$$

The left hand side is divisible by $p$ because $p$ divides $ab$. This shows that $b$ is divisible by $p$.

Now you can use this to prove the result for an arbritary product $a_1 \cdots a_n$, by using induction on the number of factors. What if the theorem were true for all products with $n-1$ factors? Hint: integer multiplication is associative.

• I think I've done exactly the same thing that you have with Euclid's example just with an arbitrary product. I would really like to do this with induction, though. I would appreciate another hint :-) – kvmu May 8 '13 at 6:14