11I think this is also given in Aurthur Engel.
This is a brilliant brilliant proof i read today...
This is from a book called problem solving strategies... (it is a brilliant read!)
-
UP 0 DOWN 0 2 11
11 Answers
62Some of you may not be able to understand cyclic permutation.. but for them think that it is same as circular arrangement on a table... :)
1First, we are talking about Fermat's little theorem, not Fermat's last theorem. So please correct the title of the post.
(http://en.wikipedia.org/wiki/Fermat's_little_theorem)
Second, Fermat's little theorem needs p to be a prime. The exact statement is this: If p is a prime then for any integer a, ap is congruent to a mod p. (i.e. ap-a is divisible by p).
Your argument is incomplete because it "assumes" (without explicitly stating) that there are p cyclic permutations of p pearls on a string for a given necklace. It should be made clear that such a guarantee is possible only when p is a prime.
For example, let P = 4 and a = 2. suppose there are pearls with 2 colors, R and B. The observe that a necklace RBRB does not have four cyclic permutations, it has only 2.
So it must be made clear that p cyclic permutations for a necklace are possible because p is a prime.
Rest all looks fine. I would still prefer to have a different version of this argument that uses "circular table" with 'P' people sitting around it (and wearing caps of 'A' different colors) rather than having necklaces. The reason is that necklaces can (theoretically) be flipped, which means that there might be more than p permutations of p pearls on a string that correspond to the same necklace when p is a prime.
Hope this helps. Thanks!
39Gosh..I was thinking this topic was wrong because Fermat's last theorem states that xn + yn ≠zn where n > 2(I have a book called Fermat's Last Theorem by Simon Singh, it goes through the history of this proof which Andrew Wiles finally achieved using Iwasawa theory and elliptic curves or something like that)...but some people would discourage me by sarcastically calling me a genius, fearing that I didn't comment.
1@Soumik, You probably meant that k|(ak-a) where (a,k) need not be 1.
That is not correct. Use a=2, k = 4. Then ak -a = 16-2 = 14, and k (= 4) does not divide 14.
If you actually meant what you wrote, still it is wrong, use the same values of a and k to get a contradiction.
Of course there can be instances where k divides ak-a even when (a,k) != 1. For example, let a = 4, k = 2 and then the identity would hold. But that is more of a "special scenario" and such a general rule holds only when when k is a prime. Note that Fermat's little theorem talks about k being a prime, and not about (a,k) being 1.
Of course if (a,k) =1 and k is prime, then we get another equivalent congruence that ak-1 ≡ 1 (mod k).
11Tell u something - the thing proved here is not Fermat's theorem.
Fermat's theorem is the one u mentioned at the end....k|(ak-a) does not imply ak-1≡1(mod k).
Yes, for Fermat's theorem, we need (a,k) to be 1, but not for this one.
1completely agree wit soumik
but tis is the original statement of fermat's theorem k l(a^k-a)
@u2001137 see wikipedia or any standard text k l (a^k-a) requires tat only k be prime n no other condition u used k=4 not a prime
for a^k-1≡1(mod k) ..(a,k)=1 is also needed but not for first one