# Provide a Combinatorial proof of Fermat's little theorem

Give a combinatorial proof of Fermat’s little theorem. Fix an integer $a≥1$ and a prime $p$. Let $$S=\{(x_1,x_2,...,x_p)\in \mathbb{Z}^p |1 \leq x_i \leq a\}$$ for all i.

Let T denote the subset of constant sequences $$T = \{(1,1,...,1),(2,2,...,2),...,(a,a,...,a)\}$$

Define a map $r: S \rightarrow S$ by rotation as follows: $$r(x_1,...,x_p) = (x_p,x_1,x_2,...,x_{p−2},x_{p−1})$$

For each integer $j \geq 1$ let $r^j$ denote the repeated rotation defined by $r\circ r\circ ···\circ r$.

Say that $x ∈ S$ has order $j$ if $j$ is the smallest integer with $j ≥ 1$ such that $r^j(x) = x$

1. How many elements do each of S and T contain?
2. Prove that $r^p$ is the identity map. (1 points)
3. Prove that $x ∈ S$ has order one if and only if $x ∈ T$. Otherwise prove that $x$ has order $p$.
4. Deduce that $p$ divides the order of the set $S$\ $T$ . (Hint : group the elements of $S$ \ $T$ into groups of rotationally related elements, and use part 3)
5. Deduce that $ap ≡ a (mod p)$

I'd appreciate any tips for any of the steps. Currently, I think that for

1) there are $a^p$ elements in $S$ and $a$ elements in $T$

2) So if there is $a^p$ elements, then $r^p$ rotations, you will eventually end up with S again (ex: 3 elements 1,2,3 -> 3,1,2 -> 2,3,1 ->1,2,3 over the 3 rotations), there for $r^p$ on S yields S, right?

3) Since T is made up of constant sequences, the order will always be 1 for elements of T (1,1,1 -> 1,1,1 -> 1,1,1 after rotations by r). I'm unsure of how to prove x has order p for non T element x's. Can I say that $r^p$ rotations of S will result in the identity, which is the finite group $g^n=I$?

• Let $E=\mathbb{Z}/(p\mathbb{Z})^*$. Then for any $a\in E$, the map sending $x\in E$ to $ax\in E$ is bijective, hence $$a^{p-1}(p-1)!\equiv \prod_{x\in E}(ax)\equiv \prod_{x\in E}x \equiv (p-1)!\pmod{p}$$ and since $(p-1)!\not\equiv 0\mod{p}$, $$a^{p-1}\equiv 1\pmod{p}$$ follows. – Jack D'Aurizio Oct 26 '16 at 2:03

1. Yes, $S$ has $a^p$ elements, but $T$ has way fewer. You can count them from the description of $T$ you gave.
2. The identity map from $S\to S$ is the map that takes $(x_1,\dotsc, x_p)$ to $(x_1, \dotsc, x_p)$ for any element $(x_1,\dotsc, x_p)\in S$. Saying that $r^p$ is $S$ doesn't make sense - $r^p$ is a map from $S$ to $S$, and $S$ is a set. Perhaps if you said in words what $r$ did to an element of $S$, you'd find it easier to see what $r^p$ (applying $r$ $p$ times) does.
3. An element has order one if $r(x_1, \dotsc, x_p) = (x_1, \dotsc, x_p)$. What elements of $S$ have this property? (You might want to use your verbal description of $S$ from part 2).
• T must have $a$ constant sequences then, right? And it looks like r takes the last element of S and places it at the first position in S. Oh! would this not just continuously re-order the set? 1,2,3 would be 3,1,2, then 2,3,1, and then back to 1,2,3? – knames Oct 26 '16 at 2:01