Proving something is commutative in abstract algebra

[snesnerd]

If \ast : (f \ast g)(n) = \sum\limits_{d|n}f(d)g(\frac{n}{d}), show that \ast is commutative. Note that d|n says d divides n. Now I was not sure how to do this from an abstract algebra point of view although when I stare at it my though process was to maybe rewrite it somehow, which will then be easier to show its commutative.

Homework Statement

Homework Equations

The Attempt at a Solution

 

[pasmith]

If \ast : (f \ast g)(n) = \sum\limits_{d|n}f(d)g(\frac{n}{d}), show that \ast is commutative. Note that d|n says d divides n. Now I was not sure how to do this from an abstract algebra point of view although when I stare at it my though process was to maybe rewrite it somehow, which will then be easier to show its commutative.

If d|n then there exists a unique positive integer c such that cd = n.

 

[brmath]

start by writing down g*f(n).

 

[snesnerd]

I understand what you mean pasmith, but I don't see how that would help show it is commutative.

 

[Dick]

I understand what you mean pasmith, but I don't see how that would help show it is commutative.

Put, say n=6. Write out the sum f*g(6). Then write out g*f(6). Can you see why they are equal? That's what pasmith's hint is leading to.

 

[snesnerd]

Okay if that is the case, would the following proof show that it is commutative:

(f \ast g)(n) = \sum\limits_{d|n}f(d)g(\frac{n}{d}) = \sum\limits_{d|n}f(\frac{n}{c})g(c) = \sum\limits_{d|n}g(c)f(\frac{n}{c}) = (g \ast f)(n)

 

[Dick]

Okay if that is the case, would the following proof show that it is commutative:

(f \ast g)(n) = \sum\limits_{d|n}f(d)g(\frac{n}{d}) = \sum\limits_{d|n}f(\frac{n}{c})g(c) = \sum\limits_{d|n}g(c)f(\frac{n}{c}) = (g \ast f)(n)

By itself, it doesn't make any sense. You have to work in the statement of how d is related to c and supply a few words of explanation.

 

[snesnerd]

(f \ast g)(n) = \sum\limits_{d|n}f(d)g(\frac{n}{d}).

Note that if d|n then their exists a c such that n = cd. Then d = \frac{n}{c} and c = \frac{n}{d}. Substituting above gives us:

\sum\limits_{d|n} f(\frac{n}{c})g(c)

Now from here how would I word it to explain why \sum\limits_{d|n}f(\frac{n}{c})g(c) = \sum\limits_{d|n}g(c)f(\frac{n}{c})?

 

[Dick]

(f \ast g)(n) = \sum\limits_{d|n}f(d)g(\frac{n}{d}).

Note that if d|n then their exists a c such that n = cd. Then d = \frac{n}{c} and c = \frac{n}{d}. Substituting above gives us:

\sum\limits_{d|n} f(\frac{n}{c})g(c)

Now from here how would I word it to explain why \sum\limits_{d|n}f(\frac{n}{c})g(c) = \sum\limits_{d|n}g(c)f(\frac{n}{c})?

You want to explain why the set of divisors of n, and the set of numbers n/d where d is a divisor of n are exactly the same set of numbers.

 

[snesnerd]

Because if you consider the set of divisors of n which are cd, and you substitute \frac{n}{d} in for c then you get that n = (\frac{n}{d})d = n.

 

[Dick]

Because if you consider the set of divisors of n which are cd, and you substitute \frac{n}{d} in for c then you get that n = (\frac{n}{d})d = n.

Ok, so if you sum f(d)*g(n/d) over all the divisors of n, then if you substitute the variable c=n/d (which also runs over all divisors of n) then you get the sum f(n/c)*g(c). There is a one-to-one correspondence between d and c.

 

[snesnerd]

But since we have that n and \frac{n}{d} are essentially the same set of numbers then then \frac{n}{c} and c are the same set of numbers so we can commute them and nothing will change/

 

[Dick]

But since we have that n and \frac{n}{d} are essentially the same set of numbers then then \frac{n}{c} and c are the same set of numbers so we can commute them and nothing will change/

Yes. Summing over the divisors of 6, {1,2,3,6} then f*g(6)=f(1)g(6)+f(2)g(3)+f(3)g(2)+f(6)g(1) and g*f(6)=g(1)f(6)+g(2)f(3)+g(3)f(2)+g(6)f(1). Of course, they are the same. You can match up each term in one sum with the corresponding one in the second.