Number Theory Proof

**Saint22** · November 12th 2008, 05:18 PM

Could anyone assist me with this problem...

"Use mathematical induction to prove the following generalization.
Suppose $a_1, a_2, ..., a_n$ are integers and p is a prime number. If $p|a_1 a_2 ... a_n$ , then $p|a_i$ for some $i = 1, 2, ..., n$ ." [Hint: The induction step has two cases.]

I believe I can use this theorem without proof:
Suppose a and b are integers and p is a prime number. if p|ab, then p|a or p|b. This theorem comes from the uniqueness of prime factorization section.

**o_O** · November 12th 2008, 07:07 PM

Let $P_n$ be the statement that if $p \mid a_1 a_2 \cdots a_n$ , then $p \mid a_i$ for some $i \in [1, n]$ .

Base case: $P_1$ is a trivial statement. $P_2$ is the theorem you have.

Inductive Step:
Assume $P_k$ to be true, that is, if $p \mid {\color{red}a_1 a_2 \cdots a_k}$ then $p \mid a_i$ for some $i \in [1, k]$ . It remains to show that $P_{k+1}$ also holds, that is, if $p \mid a_1 a_2 \cdots a_k a_{k+1}$ , then $p \mid a_j$ for some $j \in [1, k+1]$ .

So if we have that $p \mid ({\color{red}a_1a_2 \cdots a_k}){\color{blue}a_{k+1}}$ , by your theorem, we have 2 cases: (1) $p \mid {\color{red}a_1a_2 \cdots a_k}$ or (2) $p \mid {\color{blue}a_{k+1}}$ .

(1) By the inductive hypothesis, we already have some $j$ such that $p \mid a_j$ , namely $j = i$ .

(2) Then let $j = k+1$ and we're done.

Thread: Number Theory Proof

LinkBack

Thread Tools

Display

Number Theory Proof

Similar Math Help Forum Discussions

[SOLVED] number theory: proof required!

number theory proof

number theory proof

Number Theory Proof

Number theory proof

Search Tags