(open) Little Fermat Proof

  • Constructive Proofs
  • Thread starter fresh_42
  • Start date
  • Tags
    Proof
In summary, we use combinatoric means to show that for a prime number p and a positive integer a, p divides (a^p - a). By considering chains of colored pearls, we can see that there are a total of N orbits, or distinct rotations, of a chain with p colors and a total of a^p + (p-1)a chains. By rearranging and subtracting pa, we can see that p divides (a^p - a), without the need for group theory and Burnside's Lemma.
  • #1
fresh_42
Mentor
Insights Author
2023 Award
19,325
25,039
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.
 
Physics news on Phys.org
  • #2
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.
 
  • Like
Likes fresh_42
  • #3
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 to (open) Little Fermat Proof

What is the Little Fermat Proof?

The Little Fermat Proof is a mathematical proof that is used to demonstrate the validity of the Fermat's Little Theorem. This theorem states that if p is a prime number, then for any integer a, a^p - a is divisible by p.

How does the Little Fermat Proof work?

The proof works by using the concept of modular arithmetic. It shows that if p is a prime number, then a^p - a will always be divisible by p, no matter what the value of a is. This is because in modular arithmetic, we can reduce large numbers to smaller ones by taking the remainder when divided by p.

Why is the Little Fermat Proof important?

The Little Fermat Proof is important because it provides a way to quickly check if a number is prime or not. This is useful in many areas of mathematics and computer science, such as cryptography, where prime numbers are used to generate secure keys.

What is the difference between the Little Fermat Proof and the Fermat's Last Theorem?

The Little Fermat Proof and the Fermat's Last Theorem are two different mathematical concepts. The Little Fermat Proof deals with prime numbers and modular arithmetic, while the Fermat's Last Theorem states that no three positive integers a, b, and c can satisfy the equation a^n + b^n = c^n for any integer value of n greater than 2.

Are there any limitations to the Little Fermat Proof?

Yes, there are some limitations to the Little Fermat Proof. It only works for prime numbers, so it cannot be used to determine the primality of composite numbers. Also, there are some rare cases where the proof may not hold, known as pseudoprimes.

Similar threads

  • Math Proof Training and Practice
Replies
8
Views
2K
  • Math Proof Training and Practice
Replies
0
Views
1K
  • Math Proof Training and Practice
Replies
10
Views
1K
  • Math Proof Training and Practice
Replies
1
Views
1K
  • Math Proof Training and Practice
3
Replies
80
Views
5K
  • Math Proof Training and Practice
2
Replies
61
Views
6K
  • Math Proof Training and Practice
3
Replies
100
Views
7K
  • Math Proof Training and Practice
3
Replies
93
Views
11K
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Math Proof Training and Practice
2
Replies
42
Views
7K
Back
Top