|
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 n
p
-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 n
p
-n )
Hence Fermat’s Little Theorem is proved.
Your Password:
Prof. Ashay Dharwadker