Results 1 to 8 of 8

Math Help - Divisibility proof

  1. #1
    Member rowe's Avatar
    Joined
    Jul 2009
    Posts
    89

    Divisibility proof

    a,b,c,n,m \in \mathbb{Z}

    If a|b and a|c, show that a|(bm+cn).

    Proof:

    I have already proved that if x|y, and y|z, then x|z.

    So, if a|b, then b|bm, so a|bm.

    Also, if a|c, then c|cn, so a|cn.

    So I think I need to show that a|aj+ai for some integers j=bm, i=cn.

    ax = aj+ai
    ax = a(j+i)

    Let x = (j+i), thus ax = ax. \blacksquare


    Could someone let me know if this proof is correct?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    May 2010
    Posts
    98
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,569
    Thanks
    1410
    Quote Originally Posted by rowe View Post
    a,b,c,n,m \in \mathbb{Z}

    If a|b and a|c, show that a|(bm+cn).

    Proof:

    I have already proved that if x|y, and y|z, then x|z.

    So, if a|b, then b|bm, so a|bm.

    Also, if a|c, then c|cn, so a|cn.

    So I think I need to show that a|aj+ai for some integers j=bm, i=cn.

    ax = aj+ai
    ax = a(j+i)

    Let x = (j+i), thus ax = ax. \blacksquare


    Could someone let me know if this proof is correct?
    proof of what? Your last statement is "thus ax= ax" which is NOT what you wanted to prove! I see no reason to change from b and c to x and y.

    Since a|b, b= ap for some integer n. Since a|c, c= aq for some integer q.

    Now, bm+ cn= apm+ aqn.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by rowe View Post
    a,b,c,n,m \in \mathbb{Z}

    If a|b and a|c, show that a|(bm+cn).

    Proof:

    I have already proved that if x|y, and y|z, then x|z.

    So, if a|b, then b|bm, so a|bm.

    Also, if a|c, then c|cn, so a|cn.

    So I think I need to show that a|aj+ai for some integers j=bm, i=cn.

    ax = aj+ai
    ax = a(j+i)

    Let x = (j+i), thus ax = ax. \blacksquare


    Could someone let me know if this proof is correct?
    The part marked in red is a bit muddled. It would be better to write that: a|x and a|y => a|x+y.

    Also, as was noted, you did not end up with what you wanted to prove.

    If you know modular arithmetic notation, this proof is a lot shorter. We have

    b\equiv 0\ (\text{mod}\ a)

    c\equiv 0\ (\text{mod}\ a)

    So bm+cn\equiv 0\cdot m+0\cdot n\equiv 0\ (\text{mod}\ a)

    Of course this relies on the properties of the congruence relation, which would be proven separately.

    Also, you misuse the word "then" marked in blue. Of course "p implies q" holds if "q" is always true, but it is misleading in your proof.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member rowe's Avatar
    Joined
    Jul 2009
    Posts
    89
    Hope this is an improvement:

    a,b,c,n,m,i,j \in \mathbb{Z}

    If a|b and a|c, show that a|(bm+cn).

    Proof:

    If a|b, and b|bm then a|bm, implying aj = bm.

    Also, if a|c, and c|cn then a|cn, implying ai = cn.

    We let x = (j+i).

    ax = aj+ai
    ax = bm+cn

    Which implies a|(bm+cn). \blacksquare
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by rowe View Post
    Hope this is an improvement:

    a,b,c,n,m,i,j \in \mathbb{Z}

    If a|b and a|c, show that a|(bm+cn).

    Proof:

    If a|b, and b|bm then a|bm, implying aj = bm.

    Also, if a|c, and c|cn then a|cn, implying ai = cn.

    We let x = (j+i).

    ax = aj+ai
    ax = bm+cn

    Which implies a|(bm+cn). \blacksquare
    It works, except that I would be more careful with the part I marked in red (and the analogous part right below it); I would state as either:

    implying there exists j such that aj = bm.

    implying aj = bm for some j.

    But take a look at HallsofIvy's post for a short proof that doesn't use the congruence notation I mentioned.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member rowe's Avatar
    Joined
    Jul 2009
    Posts
    89
    Thanks, I "declared" j and i above as i,j \in \mathbb{Z}
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by rowe View Post
    Thanks, I "declared" j and i above as i,j \in \mathbb{Z}
    I'm guessing you have programming experience.

    I understand your intent, but I still think it's an abuse of notation. Consider:

    1: Let u,v\in \mathbb{Z}. Suppose u is a perfect square. Then u=v^2.

    and

    2: Let u\in \mathbb{Z} be a perfect square. Now let v\in \mathbb{Z}. Then u=v^2.

    Note that (1) and (2) essentially are the same, but with the order of declaration changed.

    You see how this wording suggests that any integer v satisfies u=v^2, rather than some integer v?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Help with divisibility proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: January 23rd 2011, 11:39 AM
  2. divisibility proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 13th 2010, 11:05 AM
  3. divisibility proof
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 16th 2009, 08:39 PM
  4. divisibility proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: January 20th 2009, 10:27 PM
  5. Divisibility proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: September 10th 2008, 07:07 AM

Search Tags


/mathhelpforum @mathhelpforum