# induction..prime number proof

• Nov 29th 2010, 11:13 PM
mremwo
induction..prime number proof
confused:

[im indicating a subscript by parenthesis... as in a sub 1 = a(1) not multiplying]

By PMI, prove that this statement is true:
"If p is a prime number and p | a(1)*a(2)...a(n), where a(i) is an integer for i=1,2,3...n then p | a(i) for some integer i.

(im especially confused at what the make my proposition P(k) and where to substitute the k for PMI.)
thank you so much
• Nov 30th 2010, 12:44 AM
emakarov
Yes, formulating P(k) is the key in constructing a proof by induction.

Here, in fact, you have a standard case. If your theorem can be formulated as, "For all integers n >= n0, P(n)", then usually you can take P(n) as the induction statement. Here the theorem is, "For all integers n >= 1, for all primes p and sequences of integers a(1), ..., a(n), if p | a(1) * ... * a(n), then p | a(i) for some i". So, just strip the universal quantification over n and you get your P(n).

The base case for n = 1 is obvious, and for the induction step you need to use Euclid's lemma.
• Nov 30th 2010, 07:25 AM
mremwo
thats really helpful, thanks.

but now im stuck after doing the base case.
im not very good at induction, so some help on the induction step would be awesome, thanks

Quote:

Originally Posted by emakarov
Yes, formulating P(k) is the key in constructing a proof by induction.

Here, in fact, you have a standard case. If your theorem can be formulated as, "For all integers n >= n0, P(n)", then usually you can take P(n) as the induction statement. Here the theorem is, "For all integers n >= 1, for all primes p and sequences of integers a(1), ..., a(n), if p | a(1) * ... * a(n), then p | a(i) for some i". So, just strip the universal quantification over n and you get your P(n).

The base case for n = 1 is obvious, and for the induction step you need to use Euclid's lemma.

• Nov 30th 2010, 08:47 AM
emakarov
The induction hypothesis: for all primes p and sequences of integers a(1), ..., a(n), if p | a(1) * ... * a(n), then p | a(i) for some i.

Need to prove: for all primes p and sequences of integers a(1), ..., a(n), a(n+1), if p | a(1) * ... * a(n) * a(n+1), then p | a(i) for some i.

Proof outline. Fix a prime p and n+1 integers a(1), ..., a(n+1). Assume that p | a(1) * ... * a(n) * a(n+1). Denote A = a(1) * ... * a(n), so p | A * a(n+1). Now apply Euclid's lemma. If p | a(n+1), we are done. If p | A, apply the induction hypothesis.