Can you help me to proof the Fermat theorem that if p is a prime number, then n^p - n can be divided by p.

Thank you,

Ngoc

Here's a nice proof that I once came across:

Suppose I am making bracelets by threading beads on a piece of string and tying the ends together. I have n different colours of beads, and each bracelet has exactly p beads on it.

Now, how many different bracelets can I make? Clearly, if I were just making strings of beads, I could make n^p , because I have n choices for the colour of the first bead, n for the second, and so on up to the p^th bead.

However, I'm closing them up into loops. Now, for example, let's represent a black bead by O and a white one by X.

Then if I make O-X-X-O-O, and join the ends together, and I also make X-X-O-O-O, I will get the same bracelet in the end, because I can just slide beads past the knot in the string. By doing this, there are 5 different strings that all give the same bracelet.

So, for any arrangement like the O-X-X-O-O one for p=5, I have a set of p different strings that give the same bracelet.

However, if I had the string O-O-O-O-O, this isn't in any of these groups - it looks the same wherever you start from, so to speak.

In fact, there will be precisely n single-coloured strings like this one, because there are n colours. The other n^p -n strings will fall into groups of size p. Hence if the number of these groups is k then k×p = n^p -n.

(Can you see why this doesn't work if p isn't a prime?)

David

Of course, there are many more advanced proofs - if you know enough group theory it's obvious - but this is one of the neatest and easiest.

nice proof David..

love arun

David, where did you use that p is prime, in your proof?

Abbas, the point is that if you have a string that is invariant under a cyclic rotation by k places, then k must divide p. So for p prime, k is 1 or p, which is why the proof works. If p isn't prime it breaks down. For example, if p=4, then O-X-O-X is in a group of 2, with X-O-X-O and nothing else.

Also, it is all very well deriving Fermat from the Fermat-Euler theorem, but how do you propose to prove this theorem? It is obvious that Fermat's follows from Euler's, but that doesn't really get us anywhere without a proof of the latter. (Of course Fermat-Euler is also obvious from a group theoretic perspective.)

David

ANOTHER PROOF:
Let p be a prime number.

(x+1)p=

p å i=0

p Ci xi

Now it can be easily proved that,

(x+1)^p=x^p+1 (mod p)....(1)

now i define f(x)=x^p-x

Note: now we need to prove that f(x)=0 (mod p)

Now eqn (1) can be written as,

f(x+1)=f(x) (mod p).....(2) (this result is imp.)

now we will use induction to prove our statement i.e f(x)=0 (mod p)
PART I :
it is seen that f(x)=0 (mod p) is true for x=0 and

PART II :
Assume that f(x)=0 (mod p) is true for x=k

i.e f(k)=0 (mod p).....(3)

PART III :
now we will prove that the result is true for x=k+1
Now,
f(k+1)=f(k)(mod p)........(from (2) above)
but f(k)=0(mod p).......(from (3) above)
therefore,
f(k+1)=0(mod p)

therefore,f(x)=0(mod p) is true for all x positive integers.....
but f(x)=x^p -x
therefore,
x^p -x=0(mod p)
hence,
x^p =x(mod p)

QED
love arun

Thanks everyone. I got it now.