Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

how to prove that $\forall n \in \mathbb{N^+}, \forall p \in \mathbb{P} ,\forall a \in \mathbb{(N^+)^n}, p|(\prod^n_{i=1} a_i) \Rightarrow (\exists k \in {1,2,3,\ldots,n }, p|a_k)$ ?

PS:$\Bbb{P}$ is prime number.

share|cite|improve this question
You may want to explain what $\Bbb P$ is, and what you did to try and solve this question. – Asaf Karagila Mar 8 '13 at 21:23
So $\mathbb P$ is the set of prime numbers, I guess. You should specify that. – 1015 Mar 8 '13 at 21:25
the $\Bbb{P}$ is the prime number, I try to find the base case, but i don't know what is the base case, because $n ,p, a$ can be any number (follow the rules). – tywtyw2002 Mar 8 '13 at 21:26
up vote 3 down vote accepted

Hint: If $p$ is a prime number and $p\mid a\cdot b$ then either $p\mid a$ or $p\mid b$. This is the case for $n=2$. If you haven't proved this, you should do so explicitly.

Then use the fact that multiplication is associative and deduce the general case by considering $b=\prod_{i=1}^{n-1}a_i$ and $a=a_n$, and using the induction hypothesis if needed.

The quantifiers may seem confusing, but the approach would be to do the induction over $n$, then take $p$ to be an arbitrary prime number, and $a=(a_1,\ldots,a_n)$ an arbitrary $n$-tuple. Of course it might not be the case that $p$ divides the product of the $a_i$'s, but that case doesn't interest us.

So we prove by induction on $n$, take $p$ to be an arbitrary prime number, and $a$ to be an arbitrary tuple.

The base case is for $n=1$, of course, in which case there is nothing to prove. $a=a_1$ and by assuming $p\mid a_1$ we have that $p\mid a_1$. The real base case is for $n=2$ as my hint above points out.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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