- #1

Benny

- 584

- 0

I was told that the following can be proven by induction. Can someone explain to me how this can be done?

I also have the following fact: If p|(ab) then either p|a, p|b or both.

Let p be a prime number and let a_i, i = 1,2,3,...,n be integers. If p|(a_1)(a_2)...(a_n) then p divides at least one of the a_i.

I'm not too sure how to state the the induction proposition/statement. Perhaps P_n is the statement that if p|(a_1)(a_2)...(a_n), p is prime and the a_i are integers then p divides at least one of the a_i. But what about the base case? I guess the base case just follows from the fact which I included earlier in this post. So how would I prove that p_k is true => p_(k+1) is true.

The induction hyhpothesis would be if p|(a_1)(a_2)...(a_k) where p is prime and the a_i are integers, then p divides at least one of the a_i. Would I then write p_(k+1) is also true because:

[tex]

a_1 a_2 ...a_k a_{k + 1} = a_{k + 1} \left( {a_1 a_2 ...a_k } \right)

[/tex]

[tex]p|a_1 a_2 ...a_k[/tex] by hypothesis so that:

[tex]

p|a_{k + 1} \left( {a_1 a_2 ...a_k } \right)

[/tex]

Any help would be good.

I also have the following fact: If p|(ab) then either p|a, p|b or both.

Let p be a prime number and let a_i, i = 1,2,3,...,n be integers. If p|(a_1)(a_2)...(a_n) then p divides at least one of the a_i.

I'm not too sure how to state the the induction proposition/statement. Perhaps P_n is the statement that if p|(a_1)(a_2)...(a_n), p is prime and the a_i are integers then p divides at least one of the a_i. But what about the base case? I guess the base case just follows from the fact which I included earlier in this post. So how would I prove that p_k is true => p_(k+1) is true.

The induction hyhpothesis would be if p|(a_1)(a_2)...(a_k) where p is prime and the a_i are integers, then p divides at least one of the a_i. Would I then write p_(k+1) is also true because:

[tex]

a_1 a_2 ...a_k a_{k + 1} = a_{k + 1} \left( {a_1 a_2 ...a_k } \right)

[/tex]

[tex]p|a_1 a_2 ...a_k[/tex] by hypothesis so that:

[tex]

p|a_{k + 1} \left( {a_1 a_2 ...a_k } \right)

[/tex]

Any help would be good.

Last edited: