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$?

  • 1
    $\begingroup$ 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. $\endgroup$ – Jack D'Aurizio Oct 26 '16 at 2:03

Some starting hints:

  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).

  • $\begingroup$ 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? $\endgroup$ – knames Oct 26 '16 at 2:01
  • $\begingroup$ Yes, that's right. So perhaps you can make some progress now; if you do, you should add it to your original post and then tell us where you're then stuck (if you are). $\endgroup$ – rogerl Oct 26 '16 at 2:04
  • $\begingroup$ Fantastic, I will do that, thank you very much! $\endgroup$ – knames Oct 26 '16 at 2:06
  • $\begingroup$ I've updated my original question, does part 3 make sense, or am I on the wrong track? Thanks again! $\endgroup$ – knames Oct 26 '16 at 2:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.