(open) Little Fermat Proof

  • Constructive Proofs
  • Thread starter fresh_42
  • Start date
  • #1
fresh_42
Mentor
Insights Author
2022 Award
17,645
18,308
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
fishturtle1
394
81
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
fresh_42
Mentor
Insights Author
2022 Award
17,645
18,308
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

Suggested for: (open) Little Fermat Proof

  • Last Post
Replies
4
Views
770
Changing the Statement (open) Zeta(2)
  • Last Post
Replies
7
Views
615
  • Last Post
Replies
0
Views
592
  • Last Post
Replies
2
Views
489
  • Last Post
Replies
10
Views
609
  • Last Post
Replies
1
Views
460
Constructive Proofs Proof of Correspondence theorem
  • Last Post
Replies
1
Views
553
  • Last Post
Replies
5
Views
678
  • Sticky
  • Last Post
Replies
0
Views
688
Top