Thread: 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?

I would just go straightforward and say that

and , where

We want to show that where * denotes multiplication mod 6.

Regular multiplication of a and b yields .

Since regular multiplication is commutative, then

Originally Posted by Ragnarok

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 means that is divisible by .
In this case since in the reals is divisible .

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)

Thanks so much for your help!

Since it's modulo 6, why not just draw up an addition table and a multiplication table?

@Prove It, problem is, how would you generalize that to any modulus. Fortunately we're only dealing with mod 6.

one can see commutativity at a glance from looking at a multiplication table (symmetry about the diagonal). associativity is not so self-evident.