# Thread: Proof of an LCM theorem via induction

1. ## Proof of an LCM theorem via induction

Hi,
I am having troubles proving the following theorem via induction on t, I get the base case but I am not sure how to prove it for all t:

Let a_1,..,a_t be positive integers, then lcm(a_1,..,a_t) | c iff a_i | c for all i.

Any help would be greatly appreciated,

Thanks

2. Originally Posted by RonyPony
Hi,
I am having troubles proving the following theorem via induction on t, I get the base case but I am not sure how to prove it for all t:

Let a_1,..,a_t be positive integers, then lcm(a_1,..,a_t) | c iff a_i | c for all i.

Any help would be greatly appreciated,

Thanks
Hint - Use the fact (you might be required to prove it as well)

LCM (a_1,..,a_t,a_{t+1}) = LCM (LCM (a_1,..,a_t),a_{t+1})

3. When attempting to prove it for all t+1, I started with the fact that

lcm(a_1,...,a_t+1) = lcm(lcm(a_1,...,a_t),a_t+1)

and we know lcm(a_1,...,a_t) | c which implies a_i | c for all i. but I am not sure if that concludes anything about a_t+1.

Thanks.

4. Originally Posted by RonyPony
When attempting to prove it for all t+1, I started with the fact that

lcm(a_1,...,a_t+1) = lcm(lcm(a_1,...,a_t),a_t+1)

and we know lcm(a_1,...,a_t) | c which implies a_i | c for all i. but I am not sure if that concludes anything about a_t+1.

Thanks.
Assume above holds for all n<=t
Let lcm(a_1,...,a_t) = x
Now lcm(x,a_t+1)|c iff x|c and a_t+1 | c {This is true using using induction hypothesis for n=2}

Can you take it fwd now?

5. Yes I can! Thanks!