 | Home | Sign up! | Projects | Seminars | Research Notes | Today's Lecture | About |

Update Seminar Form
 Course: Seminar Topic: Seminar Description: Fermat's little theorem states that if p is a prime number, then for any integer n, p divides np-n. This means that if you take some number n, multiply it by itself p times and subtract n, the result is divisible by p.
A proof using necklaces
Here is an interesting proof of Fermat’s Little Theorem.
We demonstrate the proof for n=2 and p=3. The general proof is not much more difficult.
Given – beads of 2 different colors – Black beads and White beads.
We want to make necklaces out of these two (this number corresponds to n) colors consisting of a total of three beads (this number corresponds to p).
For each bead in the necklace we have two choices each. Thus, for 3 beads we have a total of 8 (i.e.2^3) choices and we can link them in any combination. But out of these 8 there are 2 monochrome necklaces that we will remove since their bead arrangement will be the same, having no different combinations.
Removing the monochrome from the set, we are left with (2^3 – 2) choices.
Claim = (2^3 – 2) is divisible by 3. (Although this is obvious, remember we are trying to give a general argument!)
We will break up the necklaces into classes consisting of 3 necklaces each. E.g. taking a necklace of the combination BWW, we can rotate the beads around the necklace since they form closed necklaces. Hence we get a class {BWW, WBW, WWB}. Thus, 2^3-2 (multicolor) open necklaces make (2^3-2)/3 bracelets, each from 3 open necklaces. This shows that 3 divides (2^3-2). (Generalizing the above argument, p divides np-n )
Hence Fermat’s Little Theorem is proved. Your Password: