Thread: 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

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.

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

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.

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.