Let $w$ be a primitive $p^{th}$ root of unity, where $p$ is prime . Let $I,J \subset F_{p}$ where $F_{p}$ is a field of $p$ elements. Chebotarev's theorem states that if $I$ and $J$ have equal cardinality then the matrix $(w^{ij})_{i \in I, j\in J}$ has non-zero determinant.
What is the intuition behind this result? Note that it does not hold in general if $p$ is not prime. For example if $p=4$ then $I=\left\{0,2\right\}$ and $J=\left\{0,2\right\}$ gives a counterexample. Intuitively why doesn't it hold in general when $w$ is a primitive $n^{th}$ root of unity, $n$ being composite?