Follow-up question to "Combinatorial Proof of Fermat's Little Theorem" The original problem has been discussed here, which involves a necklace of $p$ beads each of which can be one of $a$ colors and shows that $a^p - a$ must be a multiple of $p$ by classifying the necklaces which are cyclic permutations of each other as indistinguishable and a necklace of length $p$ has $p$ cyclic permutations leading to $\frac{a^p - a}{p}$ distinct necklaces. Please see the original posting for details.
Follow-up question: Since there are $a!$ ways to permute the $a$ colors, is $\frac{a^p - a}{p}$ divisible by $a!$ ? 
Clarification: We should assume $a < p$ if not use $a \bmod p$. This will lead to such necklaces where all $a$ colors used.
 A: Suppose $a=4\,,p=3\,$
$$\frac{4^3-4}{3×4×3×2}$$
$$\frac{64-4}{4×3×3×2}$$
$$\frac{60}{4×3^2×2}$$
$$\frac{5}{6}$$
Hence disproved

The thing is, the necklaces you got may have such combinations where 1 color might have repeated less than $p$ times, $$$$(as you only discarded the ones which had 1 colour repeated $p$ times specifically)$$$$multiplying by $a!$ doesn't count those permutations

A: Your mistake is assuming that just because $a<p$ it means every color is used in every necklace.
That's not true. $a^p-a$ counts necklaces that use more than one color, and less than or equal to $a$ colors.
For example, if you take $p=5$, $a=4$, with colors Red, Blue, Green, Purple, then: "Red, Red, Blue, Blue, Blue" is counted in the $4^5-4$ necklaces. 
Under permutation of colors and rotating the necklace, this necklace is equivalent to $5\cdot 4\cdot 3$ other necklaces.
But $5\cdot 4\cdot 3=60\neq p\cdot a!=120$. And we see that $\frac{4^5-4}{5}=204$ is not divisible by $a!=24$.

Of course, when $a\geq p$ you also get the problem - if you use $p$ distinct colors, you get that any rotation is also a color permutation. So there are just $a(a-1)\cdots(a-p+1)$ elements in the equivalence class of all necklaces using $p$ distinct colors.
We can prove combinatorially that $a(a-1)$ is a divisor of $a^p-a$. 
