I was told that the following can be proven by induction. Can someone explain to me how this can be done?(adsbygoogle = window.adsbygoogle || []).push({});

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.

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Mathematical induction

**Physics Forums | Science Articles, Homework Help, Discussion**