# How do I see this? Simplification

1. Jul 27, 2011

### 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$?

2. Jul 28, 2011

### 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

$$a_0 a_1^3 a_2 a_5$$

The RHS, of course, is

$$a_0 a_1 a_2 a_3 a_4 a_5$$

Or maybe I don't understand your notation?

3. Jul 28, 2011

### 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)$