(open) Little Fermat Proof

  • Constructive Proofs
  • Thread starter fresh_42
  • Start date
  • #1
15,351
13,383
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.
 

Answers and Replies

  • #2
334
44
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.
 
  • #3
15,351
13,383
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.
 
  • Informative
Likes fishturtle1

Related Threads on (open) Little Fermat Proof

Replies
4
Views
397
Replies
7
Views
366
E
Replies
0
Views
351
Replies
1
Views
257
M
Replies
5
Views
386
  • Sticky
  • Last Post
Replies
0
Views
384
Replies
6
Views
397
Top