Some Combinatorics and Some Prime Numbers Problem statement: Let $U=\{1,2,...n\}$ and $S$ be the set of all permutations of the elements of $U$. For any $f \in S$ let $I(f)$ denotes the number of inversions (see remark) of $f$. Let $A_j$ denotes the number of permutations $f$ in $S$ such that $I(f)\equiv j\pmod{p}$ $[0\leq j \leq p-1]$ where $p$ is an odd prime number. Then prove that $$A_1=A_2=A_3=\ldots=A_{p-1} \Leftrightarrow p\leq n.$$
My solution to this problem uses roots of unity (as I have posted the answer). I want to find other solutions.
Remark For a permutation $\sigma$ of $\{1,2,\ldots,n\}$ we call a pair $(i,j)$ an inversion in $\sigma$ if $i<j$ but $\sigma(i)>\sigma(j)$.
 A: Claim 1: If $n \geq p$, then $A_0 = A_1 = \cdots = A_{p-1}$
proof: We induct on $n$. Let $B_{i,n}$ be the set of permutations on n elements with $I(f) \equiv i$ mod $p$. The base case of $n=p$ is true becasue for every $0 \leq i \leq p-1$ and way to order $2,3, \cdots, n$, there is a unique position to insert $1$ so that the resulting permutation is in $B_{i,n}$. 
Now assume the result is true for $n$. Then summing over the positions one is inserted gives $$|B_{i,n+1}| = \sum_{k = 0}^{p-1} |B_{i-k,n}|\left\lfloor\frac{(n+1-k)}{p} \right \rfloor = |B_{0, n}|\sum_{k = 0}^{p-1}\left\lfloor\frac{(n+1-k)}{p} \right \rfloor$$
so we have proven Claim 1.
Claim 2: It is not true that $A_1 = \cdots = A_{p-1}$ for $n < p$. 
proof: Let $n < p$. Suppose towards a contradiction that $A_1 = \cdots = A_{p-1}$. Considering the bijection that maps every permutation to its reversal gives $$|B_{0,n}| = \left|B_{{n \choose 2},n}\right|$$ and since $p$ does not divide ${n \choose 2}$, we get $A_0 = A_1 = \cdots = A_{p-1}$. But this is a contradiction since $p$ does not divide $n!$.
A: 
HERE IS MY SOLUTION USING ROOTS OF UNITY

Claim 1: Let $f(x)=x^{a_1}+x^{a_2}+\ldots+x^{a_m}$, where $a_1,a_2,\ldots,a_m\in \mathbb{N}$. Let $p$ be some odd prime. Denote the number of $j\in\{1,2,\ldots,m\}$ with $a_j\equiv i\pmod{p}$, for some $i\in\{0,1,\ldots,p-1\}$, by $N_i$. Let $\varepsilon=e^{\frac{2\pi i}{p}}$. Then $$f(\varepsilon)=N_0+N_1\varepsilon+N_2\varepsilon^2+\ldots+N_{p-1}\varepsilon^{p-1}$$
Proof: For $M\in\mathbb{N}$, if $M\equiv j\pmod{p}$, then $$\varepsilon^M=e^{\frac{2\pi iM}{p}}=e^{\frac{2\pi i(j+kp)}{p}}=e^{\frac{2\pi ij}{p}}e^{2\pi ik}=\varepsilon^j$$ Then, $$f(\varepsilon)=\varepsilon^{a_1}+\varepsilon^{a_2}+\ldots+\varepsilon^{a_m}$$
$$=\sum_{j=0}^{p-1}\varepsilon^j\left(\sum_{a_i\equiv j\pmod{p}}1\right)=\sum_{j=0}^{p-1}N_j\varepsilon^j$$

Claim 2: Let $b_0,b_1,\ldots, b_{p-1}\in\mathbb{Z}$. Then
$$b_0+b_1\varepsilon+b_2\varepsilon^2+\ldots+b_{p-1}\varepsilon^{p-1}=0$$ if and only if $$b_0=b_1=b_2=\ldots=b_{p-1}$$
Proof: Consider the polynomial $$\Phi_p(X)=1+X+X^2+\ldots+X^{p-1}$$ It is well known that $\Phi_p(X)$ is irreducible over $\mathbb{Z}[X]$. Again $\varepsilon$ is a root of $\Phi_p(X)$. Let $$Q(X)=b_0+b_1X+b_2X^2+\ldots+b_{p-1}X^{p-1}$$ By hypothesis $$b_0+b_1\varepsilon+b_2\varepsilon^2+\ldots+b_{p-1}\varepsilon^{p-1}=0$$ we get that $\varepsilon$ ia also a root of $Q(X)$. Since $\Phi_p(X)$ is irreducible, it is the minimal polynomial of $\varepsilon$. Then $\Phi_p(X)|Q(X)$. Since $\mathrm{deg}(\Phi_p)=\mathrm{deg}(Q)=(p-1)$, $\exists$ $a\in \mathbb{Z}$ such that $Q(X)=a\Phi_p(X)$. Therefore $$b_0=b_1=b_2=\ldots=b_{p-1}$$ The other direction is pretty easy because $\varepsilon$ is a root of $\Phi_p$.

In the book COMBINATORICS OF PERMUTATIONS by MIKLOS BONA you can find the following:
Let, $$I_n(X)=\sum_{\sigma\in S_n}X^{i(\sigma)}$$
Where for some permutation $\sigma\in S_n$(the symmetric group of order $n$) $i(\sigma)$ denotes the number of inversions in $\sigma$. In the the book mentioned above we get,
$$I_n(X)=(1+X)(1+X+X^2)\ldots(1+X+X^2+\ldots+X^{n-1})$$
Hence according to the notation in the problem and claim 1, $$I_n(\varepsilon)=A_0+A_1\varepsilon+A_2\varepsilon^2+\ldots+A_{p-1}\varepsilon^{p-1}$$
Following claim 2 we conclude that $I_n(\varepsilon)=0$ if and only if $A_0=A_1=A_2=\ldots=A_{p-1}$.
Now, $I_n(\varepsilon)=0$ if and only if $\exists$ $l\in\{1,2,\ldots,n-1\}$ such that $(1+\varepsilon+\varepsilon^2+\ldots+\varepsilon^l)=0$. Since $\varepsilon$ is an algebraic number of degree $p-1$, we must have $l\geq p-1$. Then $I_n(\varepsilon)=0$ if and only if $n-1\geq l\geq p-1$. Hence we conclude that $A_0=A_1=A_2=\ldots=A_{p-1}$ if and only if $n\geq p$.
A: @cha21 has a nice proof for the case when $p > n$, but for the $p \leq n$ there is an alternative approach for proof:
Claim: if $n \geq p$, then $A_0 = A_1 = ... A_{p-1}$
Proof: Let's define function $C_p(i)$ for permutation $p$ that counts number of inversions $(j, i)$ where $j < i$. More formally: $C_p(i) = |\{ j < i \mid p_j > p_i \}|$. 
Then, for every permutation $p$ we can define a sequence $C(p) = [C_p(0), C_p(1), ..., C_p(n - 1)]$. This sequence contained in the set of integer sequences $S(n)$ of length $n$, where $i$-th element of every sequence is in the set $[0..i]$, so $S(n) = \{ s \mid |s| = n \text{ and } \forall_i s_i \in [0..i] \}$ and $C(p) \in S(n)$. It's easy to see, that $|S(n)| = n!$ and therefore for any sequence $s \in S(n)$ there is exactly one permutation $p$ such that $C(p) = s$. 
Let's say that two sequences $a$ and $b$ from the set $S(n)$ equivalent iff $a$ and $b$ differs only at position $p-1$. This equivalence relation partition set $S(n)$ into the classes $K_i \subset S(n)$, and it's easy to see that $|K_i| = p$ and sequences from $K_i$ has $p$ different remainder of sum of values by module $p$. This implies, that $A_0 = A_1 = ... = A_{p-1}$.
