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.