Proving something is commutative in abstract algebra

  • Thread starter snesnerd
  • Start date
  • #1
snesnerd
26
0
If [itex]\ast : (f \ast g)(n) = \sum\limits_{d|n}f(d)g(\frac{n}{d})[/itex], show that [itex]\ast[/itex] is commutative. Note that [itex]d|n[/itex] says [itex]d[/itex] divides [itex]n[/itex]. 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

 
Last edited by a moderator:

Answers and Replies

  • #2
pasmith
Homework Helper
2,268
872
If [itex]\ast : (f \ast g)(n) = \sum\limits_{d|n}f(d)g(\frac{n}{d})[/itex], show that [itex]\ast[/itex] is commutative. Note that [itex]d|n[/itex] says [itex]d[/itex] divides [itex]n[/itex]. 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 [itex]d|n[/itex] then there exists a unique positive integer [itex]c[/itex] such that [itex]cd = n[/itex].
 
  • #3
brmath
329
34
start by writing down g*f(n).
 
  • #4
snesnerd
26
0
I understand what you mean pasmith, but I dont see how that would help show it is commutative.
 
  • #5
Dick
Science Advisor
Homework Helper
26,263
619
I understand what you mean pasmith, but I dont 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.
 
  • #6
snesnerd
26
0
Okay if that is the case, would the following proof show that it is commutative:

[itex](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)[/itex]
 
  • #7
Dick
Science Advisor
Homework Helper
26,263
619
Okay if that is the case, would the following proof show that it is commutative:

[itex](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)[/itex]

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.
 
  • #8
snesnerd
26
0
[itex] (f \ast g)(n) = \sum\limits_{d|n}f(d)g(\frac{n}{d})[/itex].

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

[itex] \sum\limits_{d|n} f(\frac{n}{c})g(c) [/itex]

Now from here how would I word it to explain why [itex] \sum\limits_{d|n}f(\frac{n}{c})g(c) = \sum\limits_{d|n}g(c)f(\frac{n}{c}) [/itex]?
 
  • #9
Dick
Science Advisor
Homework Helper
26,263
619
[itex] (f \ast g)(n) = \sum\limits_{d|n}f(d)g(\frac{n}{d})[/itex].

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

[itex] \sum\limits_{d|n} f(\frac{n}{c})g(c) [/itex]

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

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.
 
  • #10
snesnerd
26
0
Because if you consider the set of divisors of [itex] n [/itex] which are [itex] cd [/itex], and you substitute [itex] \frac{n}{d} [/itex] in for [itex] c [/itex] then you get that [itex] n = (\frac{n}{d})d = n [/itex].
 
  • #11
Dick
Science Advisor
Homework Helper
26,263
619
Because if you consider the set of divisors of [itex] n [/itex] which are [itex] cd [/itex], and you substitute [itex] \frac{n}{d} [/itex] in for [itex] c [/itex] then you get that [itex] n = (\frac{n}{d})d = n [/itex].

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.
 
  • #12
snesnerd
26
0
But since we have that [itex] n [/itex] and [itex] \frac{n}{d} [/itex] are essentially the same set of numbers then then [itex] \frac{n}{c} [/itex] and [itex] c [/itex] are the same set of numbers so we can commute them and nothing will change/
 
  • #13
Dick
Science Advisor
Homework Helper
26,263
619
But since we have that [itex] n [/itex] and [itex] \frac{n}{d} [/itex] are essentially the same set of numbers then then [itex] \frac{n}{c} [/itex] and [itex] c [/itex] 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.
 

Suggested for: Proving something is commutative in abstract algebra

Replies
1
Views
2K
Replies
11
Views
3K
Replies
5
Views
636
Replies
9
Views
4K
Replies
5
Views
11K
Replies
2
Views
4K
Replies
5
Views
4K
Replies
5
Views
1K
Top