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