Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2008-09-02 00:24:47

Kurre
Member
Registered: 2006-07-18
Posts: 280

Combinatorial proof of fermats little theorem

This is from the book "problem solving strategies" by Arthur Engel:

We have pearls with a colors. From these we make necklaces with exactly p pearls. First we make a string of pearls and there are a^p different strings. If we throw away the a one-colored strings a^p-a strings will remain. We connect the ends of each string to get necklaces. We find that two strings that differ only by a cyclic permutation result in indistinguishable necklaces, but there are p cyclic permutations of p pearls on a string. Hence the number of distinct necklaces is (a^p-a)/p. But this number must be an integer, thus p | a^p-a. q.e.d.

I find this proof pretty elegant, but I cant see how the proof uses that p must be a prime number? It seems that this proof shows that p | a^p-a for all natural p, but this isnt true. What am I missing?dunno

Offline

#2 2008-09-02 06:35:37

Kurre
Member
Registered: 2006-07-18
Posts: 280

Re: Combinatorial proof of fermats little theorem

Ah, nevermind, I got it, if p wasnt prime then there are some necklaces where patterns of colored pearls can repeat, and thus doesnt have p different cyclic permutations. smile

Offline

Board footer

Powered by FluxBB