# Homework Help: Algebra Proof

1. Jan 11, 2012

### Punkyc7

Let μ=(1....n)
WTS μ^(n)=ε.

I having a hard time seeing how to start the proof. It seems obvious that of you have n elements your going to need n μ's because each μ gets you one number closer to the original number. Ive tried transpositions but that didn't seem to work very well, I got lost in all the notation. Any advice would be greatly appreciated

2. Jan 11, 2012

### Staff: Mentor

perhaps you can use induction:

part 1: prove for case where k=1

then

part 2: assume its true for k and prove its also true for k+1

having said that:

What is μ? what is ε?

Is that a μ * μ * ... μ for n factors?

I'm trying to understand what you are trying to prove in your words or the teachers words.

3. Jan 11, 2012

### Punkyc7

μ is written in cycle notation. If you use induction I can't see any way to get back to the original size μ or use it the imply the n+1 μ=ε. ε is the identity

Last edited: Jan 11, 2012
4. Jan 11, 2012

### Staff: Mentor

okay so this is modula algebra so for a given set of numbers say 1 thru 12 you must show that any number in the set when raised to the 12th power is the identity element 1 right?

5. Jan 11, 2012

### Staff: Mentor

so for the identity 1 its clear that 1^n = 1

so for part 2 you can assume that for some k in the set (1...n) that k^n mod n = 1

now can you prove it for (k+1)^n mod n = 1

this seems really tough you'd need to expand the (k+1)^n into n terms and then apply mod n.

what if you set n to 1 ie set is (1) and clearly 1^1 = 1

then you'd be assuming x^k mod k =1

and you'd need to prove x^(k+1) mod (k+1) = 1

6. Jan 11, 2012

### Dick

That's not what Punkyc7 is trying to prove. And it's not even true. 2^3 mod 3 isn't equal to 1, e.g. f=(12...n) is supposed to represent a permutation in cycle notation. So f(1)=2, f(2)=3, ... , f(n)=1. The goal is to show if g=f^n (where multiplication is composition of permutations), that g is the identity permutation. I.e. g(k)=k for all k in {1,...,n}.

Last edited: Jan 11, 2012
7. Jan 11, 2012

### Punkyc7

Dick is right, that is what im trying to prove

8. Jan 11, 2012

### Staff: Mentor

Sorry but you didn't respond to my previous post so I started thinking about it a little further in terms of modulo arithmetic and proofs by induction. Please disregard my post then.

Part of my confusion that sometimes posts use keyboard approximations to math notation and thats what I thought I saw here.

9. Jan 11, 2012

### Dick

As you've already said, the proof is almost obvious. Can't you just explain it in words? I'm not sure I can think of any formal symbolism that adds much to that. If f=(i_1,i_2,i_3...i_n) then f(i_1)=i_2. f^2(i_1)=f(f(i_1))=f(i_2)=i_3. f^k(i_1)=i_{1+k}. So finally f^(n-1)(i_1)=i_n, so f^n(i_1)=f(i_n)=i_1. And there's nothing special about i_1. (i_1,i_2,i_3...i_n)=(i_2,i_3,...i_n,i_1). I think formalism here just obscures the blindingly obvious. My opinion.

10. Jan 11, 2012

### Punkyc7

that's what I was thinking but I thought there might be a slick way to write it out instead of showing what each cycle does. Thanks for taking your time to help me.