• Support PF! Buy your school textbooks, materials and every day products Here!

Proving something is commutative in abstract algebra

  • Thread starter snesnerd
  • Start date
  • #1
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
1,740
412
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
329
34
start by writing down g*f(n).
 
  • #4
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,258
618
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
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,258
618
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
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,258
618
[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
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,258
618
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
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,258
618
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.
 

Related Threads on Proving something is commutative in abstract algebra

Replies
1
Views
2K
Replies
5
Views
4K
Replies
11
Views
3K
  • Last Post
Replies
1
Views
1K
Replies
2
Views
2K
Replies
9
Views
4K
Replies
5
Views
10K
Replies
5
Views
850
Top