I'm having some trouble with this proof. Here's the question: Use mathematical induction and Euclid's Lemma to prove that for all positive integers $s$, if $p$ and $q_1, q_2, \dotsc, q_s$ are prime numbers and $p$ divides $q_1q_2\dotsb q_s$, then $p=q_i$ for some $i$ with $1 ≤ i ≤ s$.

Here's what I know: Euclid's Lemma says that if $p$ is a prime and $p$ divides $ab$, then $p$ divides $a$ or $p$ divides $b$. More generally, if a prime $p$ divides a product $a_1 a_2 \dotsb a_n$, then it must divide at least one of the factors $a_i$. For the inductive step, I can assume $p$ divides $q_1q_2\dotsb q_{s+1}$ and let $a=q_1q_2\dotsb q_s$. Then, $p$ divides $aq_{s+1}$ and either $p$ divides $a$, $p$ divides $q_{s+1}$, or $p=q_{s+1}$. I know that since $q_i$ is prime, it cannot divide $q_i$ unless $p=q_i$ for some $1 ≤ i ≤ s$. I'm just not sure how to formulate the proof. Usually with Induction I can set some property $P(n)$ and test it is true for some base like $P(0)$ or $P(1)$ for the base step. I'm unsure how to go about it here.

  • $\begingroup$ I would have thought the initial step was to show that if $p$ and $q_1$ are prime and $p$ divides $q_1$ then $p=q_1$. Since $q_1$ is prime, it only has two divisors, namely $1$ and $q_1$; so $p$ must be one of these, and $p$ cannot be $1$ as $1$ is not prime; thus $p=q_1$. $\endgroup$ – Henry Aug 20 '15 at 23:40
  • $\begingroup$ The "more generally, if a prime divides a product $a_1\cdots a_n$, then $\dots$" is basically what you are being asked to prove. True, it is clear that it is implied by the $a,b$ case, but in principle that extension to $n$ requires induction. $\endgroup$ – André Nicolas Aug 21 '15 at 0:37

First, we note that $p|q_1$ implies $p=q$ (we don't even need Euclid's lemma to see this).

Now assume that $p|q_1q_2\ldots q_k\implies p|q_1$ or $p|q_2$ or $\cdots$ or $p|q_k$.

Now consider the statement $p|q_1q_2\ldots q_kq_{k+1}$. Using Euclid's lemma, $p$ must divide one of $q_1q_2\ldots q_k$ or $q_{k+1}$. By our inductive hypothesis, we conclude that $p|q_1$ or $p|q_2$ or $\cdots$ or $p|q_k$ or $p|q_{k+1}$.

I see that this is pretty much what you did, so which part specifically are you having difficulty writing?


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.