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?

  • $\begingroup$ 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? $\endgroup$ – EuYu May 8 '13 at 4:58
  • $\begingroup$ 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$... $\endgroup$ – anon May 8 '13 at 5:12
  • $\begingroup$ @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$. $\endgroup$ – kvmu May 8 '13 at 6:00
  • $\begingroup$ @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? $\endgroup$ – EuYu May 8 '13 at 6:06
  • $\begingroup$ @EuYu $a_i^*$ is the product $a_1\cdot\cdot\cdot a_n$ except without a factor of $a_i$ $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ 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 :-) $\endgroup$ – kvmu May 8 '13 at 6:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.