How do I see this? Simplification

[nonequilibrium]

How do I see that for any natural non-zero n:

\left( \prod_{1 \leq d \leq n \quad d | n} \right) \left( \prod_{0 \leq i \leq d-1 \quad \textrm{gcd}(d,i)=1} \right) a_i = \prod_{0 \leq i \leq n-1} a_i?

 

[pmsrw3]

I would say this is going to be hard to prove. EXCEEDINGLY hard to prove. Because... it's not true. For instance, letting n = 6, the LHS is

<br /> a_0 a_1^3 a_2 a_5<br />

The RHS, of course, is

<br /> a_0 a_1 a_2 a_3 a_4 a_5<br />

Or maybe I don't understand your notation?

 

[nonequilibrium]

Well that explains why I couldn't prove it :p

I was (am) trying to prove that X^n - 1 = \left( \prod_{1 \leq d \leq n \quad d | n} \right) \Phi_d where \Phi_d = \left( \prod_{0 \leq i \leq d-1 \quad \textrm{gcd}(d,i)=1} \right) (X - \omega_d^i) where \omega_d = \exp{ (2 \pi i /d) }

The RHS of my original equation can be understood by noting that X^n-1=\prod_{0 \leq i \leq n} (X-\omega_n^i)

but I now see my error... My apologies

However, I'm still not sure how to prove the above equation, aka that

\prod_{0 \leq i \leq n} (X-\omega_n^i) = \left( \prod_{1 \leq d \leq n \quad d | n} \right) \left( \prod_{0 \leq i \leq d-1 \quad \textrm{gcd}(d,i)=1} \right) (X - \omega_d^i)