# Mathematical induction

• Mathematica
Benny
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:

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

$$p|a_1 a_2 ...a_k$$ by hypothesis so that:

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

Any help would be good.

Last edited:

Staff Emeritus
Gold Member
1. You have not shown that if some prime divides $\Pi_{i=1}^{k+1} a_i$ then it also divides some a_i from that list. What you have shown is that if some prime divides $\Pi_{i=1}^{k} a_i$, then it also divides $\Pi_{i=1}^{k+1} a_i$. This is not what is asked for.

2. Note that it does not have to be the same prime that divides the product of the k+1 integers as that which divides the product of the k integers.

Homework Helper
if p divides a_1a_2..a_k then either p divides a_1 and we are done, or p divides a_2a_3..a_k and hence by induction divides one of the a_j for j is one of 2,..,k

i think that using the second form of mathematical induction will work better.

you assume that the statement is true for any integral statement less than the number of the statement you are trying to prove.

and then you show that if all of those statements are true that it must follow that the statement in question is true.

kinda difficult to get a hang of at first, but in my class we used it to prove the fundamental theorem of arithmetic and so forth.

Staff Emeritus