Why need prime number in Fermat's Little Theorem I want to know the reason why in Fermat's Little Theorem, we need a prime number. I read it here, but may be it needs more elaboration for me to understand. I can understand that for the combinatorial interpretation of the FlT, with size of circular string being $p$, there are $p$ cyclic permutations (for each indistinguishable, by ordering, permutation) separated by rotations. But, why the division occurs only for $p$ being prime is unclear.
I would like to emphasize that I am not able to understand in abstract algebra terminology.
 A: Take $a=2$, $p=4$. We can make $16$ necklaces, of which we throw away $2$. The remaining ones cannot be grouped into sets of $4$, however, because although there are four necklaces each for some designs:
$$BWWW=WBWW=WWBW=WWWB \\
BBWW=WBBW=WWBB=BWWB \\
BBBW=WBBB=BWBB=BBWB,$$
there are only two necklaces representing one of the designs $$BWBW=WBWB.$$
Cases such as this last one can only occur for composite $p$.

After looking at such examples, let's think back to what's going on in the proof. We want to show that the number of necklaces ($a^p-a$) is a multiple of $p$. If we can divide a set of objects evenly into groups of size $p$, then we have proved that the size of the set is a multiple of $p$. In cases where such a division does not occur, we have not proved anything.
In these cases, we have divided $2^3-2$ and $2^5-2$ evenly into groups of size $3$ and $5$, respectively. However, our method of grouping did not result in uniform groups of size $4$ or $6$ when we started with $2^4-2$ or $2^6-2$ necklaces.
The reason the division into groups worked out nicely for $3$ and $5$ was precisely because $3$ and $5$ are prime. The reason it didn't work for $4$ and $6$ can be seen by looking at the cases where it failed: The failure only occurred by exploiting the fact that $4$ and $6$ have factors. If you write out every cyclic permutation of $BWBW$, you get
$$B_1W_1B_2W_2, W_2B_1W_1B_2, B_2W_2B_1W_1, W_1B_2W_2B_1,$$ but two of those are identical, so there are really only $2$. That only happens because $4=2\times 2$, so we can have repetition between the first two beads and the second two.
A: I really like this proof of Fermat's Little Theorem and hopefully by inspecting it you can see why we need the assumption that $p$ is a prime number in the proof.
Consider the reduced residue system modulo $p$, where $p$ is prime. It's $\{1,2,\dots p-1\}$. Multiply all numbers by $a$, s.t. $\gcd(a,p)=1$. Then we obtain the set $\{a,2a,\dots (p-1)a\}$. We'll prove that this set also represent the reduced residue system modulo $p$. It's enough to show that the numbers are unique modulo $p$. If we have that $na \equiv ma \pmod p$. Then we have that $p \mid (n-m)a \implies p \mid (n-m)$, by Euclid's Lemma as $\gcd(a,p) = 1$. But obviously $|n-m| \le p-1$ so we must have $n=m$. Now multiplying all elements from the two reduced residue systems we have:
$$(p-1)! \equiv a \cdot 2a \cdots (p-1)a \equiv a^{p-1}(p-1)!\pmod p \implies a^{p-1} \equiv 1 \pmod p$$
Note that the last implication isn't true in general if $p$ isn't prime, as $n \mid (n-1)!$ for all composite integers $n$. Anyway this proves that the equation $a^{n-1} \equiv 1 \pmod n$ whenever $\gcd(a,n) = 1$ is true for all primes $p$. Unfortunately it's true for some other composite integers too, called Carmichael numbers. So technically it's not a necessary condition that $p$ must be prime. But we know it's true for all primes, so $p$ being prime is a sufficient condition. But the proof that there exist Carmichael Numbers is different and can't be performed in this way, so this proof works only for prime numbers $p$.

Note that if you take $p$ to be any positive integer $n$ in a similar fashion you can prove the Euler's Theorem, i.e. $a^{\phi(n)} \equiv 1 \pmod n$ for $\gcd(a,n) = 1$. 
