Results 1 to 5 of 5

Math Help - Proof of an LCM theorem via induction

  1. #1
    Newbie
    Joined
    Jun 2010
    Posts
    11

    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
    Last edited by RonyPony; June 1st 2010 at 07:34 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Apr 2009
    Posts
    677
    Quote Originally Posted by RonyPony View Post
    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})
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jun 2010
    Posts
    11
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Apr 2009
    Posts
    677
    Quote Originally Posted by RonyPony View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Jun 2010
    Posts
    11
    Yes I can! Thanks!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Theorem involving delta function: proof by induction
    Posted in the Advanced Math Topics Forum
    Replies: 7
    Last Post: December 16th 2010, 10:51 AM
  2. Use induction to prove Fermat's Little Theorem
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: March 8th 2010, 05:36 PM
  3. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM
  4. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 01:20 PM
  5. Proof By Induction help!
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: April 29th 2008, 09:49 AM

Search Tags


/mathhelpforum @mathhelpforum