Results 1 to 8 of 8

Math Help - Prove associativity of modular multiplication

  1. #1
    Member
    Joined
    Apr 2010
    Posts
    116
    Thanks
    1

    Prove associativity of modular multiplication

    I am working with Paul Halmos's Linear Algebra Problem Book and the seventh problem asks you to show that multiplication modulo 6 is commutative and associative. As examples of multiplication modulo 6:

    4 * 5 = 2
    2 * 3 = 0
    3 * 9 = 3

    The answer in the back for this problem states that:

    If each of a and b is one of the numbers 0, 1, 2, 3, 4, 5, and if the largest multiple of 6 that doesn't exceed their ordinary product is, say, 60, so that ab = x + 60, where x is one of the numbers 0, 1, 2, 3, 4, 5, then, because ordinary multiplication is commutative, the same conclusion holds for ba.

    The reasoning to prove associativity works similarly the language and the notation have to be chosen with care but there are no traps and no difficulties.

    Unfortunately I don't totally understand this solution. I see how it works for commutativity, but I can't work it out for associativity. We want to show that

    (a*b)*c = a*(b*c)

    where * denotes multiplication modulo 6. According to the above,

    a*b = x

    because ab = x + [largest multiple of 6 not exceeding ab]. Then we can say that

    b*c = y,

    where bc = y + [largest multiple of 6 not exceeding bc]. Then what we want to prove is

    x*c = a*y

    Since xc = m + [largest multiple of 6 not exceeding xc] and ay = n + [largest multiple of 6 not exceeding ay],

    x*c = m
    a*y = n

    After this I get confused and don't know what to do. I have no idea if I'm on the right track. What confuses me is the imprecise nature of the "largest multiple of 6 not exceeding..." term. I think I should be working with that instead, but I can't think straight. Any ideas?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Jun 2012
    From
    AZ
    Posts
    616
    Thanks
    97

    Re: Prove associativity of modular multiplication

    I would just go straightforward and say that

    a = 6j+m and b = 6k+n, where a,b,j,k,m,n \in \mathbb{Z}

    We want to show that m*n = n*m (\mod 6) where * denotes multiplication mod 6.

    Regular multiplication of a and b yields ab = (6j+m)(6k+n) = 36jk + 6jn + 6km + mn \equiv mn (\mod 6).

    Since regular multiplication is commutative, then ab = ba \equiv mn (\mod 6)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1

    Re: Prove associativity of modular multiplication

    Quote Originally Posted by Ragnarok View Post
    I am working with Paul Halmos's Linear Algebra Problem Book and the seventh problem asks you to show that multiplication modulo 6 is commutative and associative. The answer in the back for this problem states that:
    [B] If each of a and b is one of the numbers 0, 1, 2, 3, 4, 5, and if the largest multiple of 6 that doesn't exceed their ordinary product is, say, 60, so that ab = x + 60, where x is one of the numbers 0, 1, 2, 3, 4, 5, then, because ordinary multiplication is commutative, the same conclusion holds for ba.
    Unfortunately I don't totally understand this solution. I see how it works for commutativity, but I can't work it out for associativity. We want to show that
    Do you understand that p \equiv q\;\bmod (m) means that p-q is divisible by m.
    In this case since ab=ba in the reals ab-ba=0 is divisible 6.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,283
    Thanks
    673

    Re: Prove associativity of modular multiplication

    for convenience, let's write a*b to mean:

    (a mod n)*(b mod n), which we define to be (ab) (mod n). ordinary integer multiplication will be written as ab, or (a)(b) (so we don't mistake 35 and (3)(5)).

    this is still a bit ambiguous, as what is meant by "a mod n" is unclear.

    what is actually happening here is we are replacing an integer ("a") by an entire equivalence class (set):

    a mod n = [a] = {k in Z: k = a + tn, for some t in Z}.

    normally, the unique "representative" of [a] between 0 and n-1 (inclusive) is used.

    so in the integers mod 6, "4" is no longer the integer 4, but rather the set of ALL integers congruent to 4 modulo 6:

    [4] = {......-14,-8,-2,4,10,16,22,.....}

    and when we say a*b, what we mean to express is:

    [a]*[b] is defined to be [ab].

    (that is, we can multiply equivalence classes by taking the product of equivalence classes to be the equivalence class of the product of two representatives).

    now, all of this may seem rather straight-forward, and a bit over-complicated, but there is a reason i'm doing this:

    when we multiply "mod 6", what we are actually doing is "normal" multiplication, followed by finding a suitable "representative" of the product (reducing mod 6).

    for example, 3 times 5 is 15, and 15 is "bigger than 6". the representative of [15] that is in {0,1,2,3,4,5} is 3:

    15 = 3 + 12 = 3 + 6(2). that is:

    [3]*[5] = [15] <---ordinary multiplication done here
    [15] = [3] <---reduction mod 6 done here

    or more succinctly: 3*5 = 3.

    perhaps it might not be entirely clear that this is "kosher".

    after all, how do we know that if we take 9*11 (since 9 = 3 (mod 6), and 11 = 5 (mod 6)), that [99] = [15] = [3]? that is, we need to show that

    [a]*[b] depends only on [a] and [b], and not just the integers a and b (since there are infinitely many choices we might have for a or b).

    one way of doing this, is to show that if [a] = [a'], and that [b] = [b'], that [ab] = [a'b'].

    that is:

    if a = a' (mod n) and
    b = b' (mod n)

    that ab = a'b' (mod n). this will prove that [ab] uniquely defines [a]*[b], so we can rest assured that our definition makes sense, no matter what we choose for a and b.

    now if a = a' (mod n)

    then a - a' = kn, for some integer k. similarly, if b = b' (mod n), then b - b' = tn, for some integer t.

    that is: a = a' + kn, and b = b' + tn, so:

    ab = (a' + kn)(b' + tn) = a'b' + (at + b'k + ktn)n.

    now at + b'k + ktn is certainly an integer, call it u.

    thus ab = a'b' + un, so ab - a'b' = un, so ab = a'b' (mod n). this works for ANY n, including 6.

    now the proof of associativity is trivial:

    (a*b)*c = ([a]*[b])*[c] = [ab]*[c] = [(ab)c] = [a(bc)] (by associativity of integer multiplication)

    = [a]*[bc] = [a]*([b]*[c]) = a*(b*c)
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Apr 2010
    Posts
    116
    Thanks
    1

    Re: Prove associativity of modular multiplication

    Thanks so much for your help!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,329
    Thanks
    1244

    Re: Prove associativity of modular multiplication

    Since it's modulo 6, why not just draw up an addition table and a multiplication table?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member
    Joined
    Jun 2012
    From
    AZ
    Posts
    616
    Thanks
    97

    Re: Prove associativity of modular multiplication

    @Prove It, problem is, how would you generalize that to any modulus. Fortunately we're only dealing with mod 6.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,283
    Thanks
    673

    Re: Prove associativity of modular multiplication

    one can see commutativity at a glance from looking at a multiplication table (symmetry about the diagonal). associativity is not so self-evident.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: May 6th 2012, 07:17 PM
  2. prove closure under multiplication for integers
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 2nd 2010, 12:15 AM
  3. Prove that Un is a group with respect to multiplication.
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: May 2nd 2010, 08:47 PM
  4. Using modular arithmetic to prove divisibility
    Posted in the Discrete Math Forum
    Replies: 15
    Last Post: February 14th 2010, 12:52 PM
  5. Replies: 2
    Last Post: May 29th 2009, 01:47 PM

Search Tags


/mathhelpforum @mathhelpforum