Combinatorial Proof Of A Number Theory Theorem--Confusion
I came across a combinatorial proof of the Fermat's Little Theorem which states that
If $p$ is a prime number then the number ($a$$p$-$a$) is a multiple of $p$ for any natural number $a$.
Let me write down the proof.
PROOF
We have pearls of $a$ colours . From these we make necklaces of exactly $p$ pearls .
First,we make a string of pearls . There are $a$$p$ different strings.If we throw away the $a$ one one -coloured pearls ($a$$p$-$a$) strings will remain.We connect the ends of each string to get necklaces.We find that two strings that differ only by a cyclic permutation of its pearls result in indistinguishable necklaces.But there are $p$ cyclic permutations of $p$ pearls on a string . Hence the number of distinct necklaces is [($a$$p$-$a$)/$p$].
Because of this interpretation this is an integer.Thus ($a$$p$-$a$) is a multiple of $p$ for any natural number $a$. [HENCE PROVED]
MY CONFUSIONS
Solution 1:
The crux lies in the statement
But there are p cyclic permutations of p pearls on a string.
We require the fact that $p$ is prime to establish that all $p$ cyclic permutations give distinct strings. Consider a string with colours $a_0a_1 \ldots a_{p-1}$. The cyclic permutations are $a_ia_{i+1} \ldots a_{i-1}$ where $0 \leq i \leq p-1$. (Note: Indices taken $\pmod{p}$)
If any $2$ cyclic permutations $a_ia_{i+1} \ldots a_{i-1}$ and $a_ja_{j+1} \ldots a_{j-1}$ give the same string, where $i \not \equiv j \pmod{p}$, then $a_i=a_j, a_{i+1}=a_{j+1}, \ldots , a_{i-1}=a_{j-1}$, i.e. $a_{i+k}=a_{j+k}$ for $0 \leq k \leq p-1$. So $a_n=a_{n+(j-i)}$ for all $n$. Thus $a_0=a_{j-i}=a_{2(j-i)}= \ldots =a_{(p-1)(j-i)}$.
Now, since $p \nmid j-i$ and $p$ is prime, $(j-i, p)=1$. Thus $0, (j-i), 2(j-i), \ldots, (p-1)(j-i)$ form a complete residue system $\pmod{p}$, so $a_0=a_1= \ldots =a_{p-1}$. But we have excluded all strings with one colour, so we get a contradiction.
Thus when $p$ is prime, we are able to establish that all $p$ cyclic permutations are distinct.
Example for how this fails when $p$ is not prime: On the other hand, let us consider $p=4$ as an example of when $p$ is not prime. We could have a string $1212$, and the cyclic permutations are only $1212$ and $2121$. If we rotate it again we get $1212$ once again. Thus there are only 2 cyclic permutations of this string and not $p=4$ permutations.
Solution 2:
The fact that $p$ is prime also readily appears when we solve this problem using the Polya Enumeration Theorem. Here we have that the group acting on the slots into which we distribute the pearls is the cyclic group $C_p$ on $p$ elemements and we have $a$ different colors. This means we have to evaluate the substituted cycle index $$Z(C_p)(Q_1+Q_2+\cdots+Q_a)_{Q_1=1, Q_2=1, \ldots, Q_a=1}.$$ But the cycle index of $C_p$ is given by $$Z(C_p) = \frac{1}{p} \sum_{d|p} \varphi(d) a_d^{p/d}.$$ There are only two divisors when $p$ is a prime. These are $d=1$ and $d=p.$ The cycle index becomes $$Z(C_p) = \frac{1}{p} (\varphi(1) a_1^p + \varphi(p) a_p^1) = \frac{1}{p}(a_1^p + (p-1)a_p^1).$$ Therefore the substituted cycle index is $$\frac{1}{p} ((Q_1+Q_2+\cdots+Q_a)^p + (p-1)(Q_1^p+Q_2^p+\cdots+Q_a^p))_{Q_1=1, Q_2=1, \ldots, Q_a=1} \\= \frac{1}{p} (a^p + (p-1)a).$$ Therefore we must have $$a^p + (p-1)a\equiv 0 \bmod p.$$ This is precisely $$ a^p -a\equiv 0 \bmod p.$$