Constructive Proofs (open) Little Fermat Proof

[fresh_42]

Show by combinatoric means that $p\,|\,(a^p-a)$ for a prime $p \in \mathbb{P}$ and a positive integer $a\in\mathbb{N}$.

Hint: e.g. consider chains of $p$ coloured pearls where $a$ is the number of colours.

 

[fishturtle1]

Proof: Let $C$ be the set of all $p$ colored chain with $a$ colors. Let $c \in C$. We denote $c = (c_1, c_2, \dots, c_p)$ to be a $p$ colored chain where $c_i$ is any of the $a$ colors. Define $\tau = (1 2 3 \dots p)$. Then $G = \langle \tau \rangle$ acts on $C$ by $\tau^k \cdot c = (c_{\tau^k1}, c_{\tau^k2}, \dots, c_{\tau^kp})$. Moreover, every element of the orbit of $c$ represents the same chain, just rotated. Hence, by Burnside's Lemma
$$N = \frac{1}{\vert G\vert} \sum_{k, 0 \le k \le p-1} F(\tau^k)$$
where $N$ is the number of orbits and $F(\tau^k)$ is the number of chains fixed by $\tau^k$. Observe,
$F(1) = a^p$ and for $k > 0$ we have $F(\tau^k) = a$ (since $p$ is prime we counted the number of mono color chains). Hence,
$$N = \frac1p(a^p + (p-1)a)$$
Rearranging and subtracting $pa$ on both sides gives
$$pN - pa = a^p - a$$
which implies $p \vert (a^p - a)$. []

Edit: I'm sorry I just read the guidelines that maybe this post was for high school? I just learned Burnside's lemma and thought this would be a good way to practice, but feel free to delete what I wrote if i should not have posted.

 

[fresh_42]

Very nice. But you could have done the same reasoning on a high school level without Burnside and group action. So if someone wants to try ... No group theory necessary here. Your proof is therefore not really by combinatorics, since they are all hidden in Burnside's Lemma.

For all high schoolers who want to try:

Distinguish unicoloured chains and those with at least two colours. Then count the possibilities to get a new, different sorting by a shift and group them.

Side effect: If you will have done so, you automatically get an insight on how Burnside's Lemma works.