0

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.

tywtyw2002
  • 89
  • 1
    You may want to explain what $\Bbb P$ is, and what you did to try and solve this question. – Asaf Karagila Mar 08 '13 at 21:23
  • 1
    So $\mathbb P$ is the set of prime numbers, I guess. You should specify that. – Julien Mar 08 '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 08 '13 at 21:26

1 Answers1

3

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.

Asaf Karagila
  • 393,674