4
$\begingroup$

Let $p$ be a prime number and $a_1, a_2, \ldots, a_n$ be integers. Prove that if $p \mid a_1a_2 \ldots a_n$, then $p \mid a_j$ for some $j$ with $1 \leq j \leq n$.

The hint was to use induction.

So for the base case ($n = 1$):

$p \mid a_1$ would imply $p \mid a_j$ for some $j$ with $1 \leq j \leq 1$, so $j$ would have to equal 1, which would say that $p \mid a_1$ which was assumed so the base case holds.

For the induction step:

I would assume that if $p \mid a_1a_2 \ldots a_k$ then it is true that $p \mid a_j$ for some $j$ with $1 \leq j \leq k$, and would have to prove that $p \mid a_1a_2 \ldots a_k \cdot a_{k + 1}$ implies that $p \mid a_j$ for some $j$ with $1 \leq j \leq k + 1$.

This is where I get stuck, I think you only have to check the case where $j = k + 1$ because if $j$ was $a_1$ through $a_k$ the initial condition would hold? But I'm not sure.

$\endgroup$
  • $\begingroup$ That's pretty much exactly right; you're not really stuck, you actually have the proof method; the k+1 case splits into the new case and the existing known case from the induction assumption. $\endgroup$ – Joffan Apr 23 '15 at 1:38
  • $\begingroup$ Again, as in your prior related question, it would help to know what results you have available.Do you know that prime $\,p\mid ab\,\Rightarrow\,p\mid a\,$ or $\,p\mid b$? That's the key property behind the induction. $\endgroup$ – Bill Dubuque Apr 23 '15 at 1:47
3
$\begingroup$

The base case is when $n=2$ and it is called Euclid's lemma.

To see how you can prove the result via induction we shall do it over $n$ (The number of factors).

Suppose that you have proved it for $n$ factors and wish to prove it for $n+1$. We must prove that if $p|a_1a_2\dots a_{n+1}$ then $p$ divides one of the $a_j$'s. Notice that $p|(a_1a_2\dots a_{n})a_{n+1}$ so by the base case $p|a_1a_2\dots a_{n}$ or $p|a_{n+1}$.

If $p|a_{n+1}$ we are done, on the other hand if $p|a_1a_2\dots a_{n}$ then by the inductive step $p|a_j$ for some $1\leq j\leq n$ so we are also done.

$\endgroup$

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.