Talk:Fermat's little theorem
From Wikipedia, the free encyclopedia
 |
|||||||||||||||||||||||
| Mathematics rating: | Start Class | Mid Priority | Field: Number theory | ||||||||||||||||||||
|
|||||||||||||||||||||||
The behaviour of recurring decimal is related to Fermat's little theorem. User who does not have knowlege about this please do not simply delete the reference to this topic.
- Ling Kah Jai 10:18, 14 Feb 2005 (UTC)
- Although I didn't remove it, you should avoid self-referential statements, such as "The Wiki page ... includes". Also, please refrain from attacking people: "added back this section which was deleted by some ignorant user". CryptoDerk 17:05, Feb 14, 2005 (UTC)
-
- Noted. --Ling Kah Jai 10:26, 15 Feb 2005 (UTC)
Maybe this should be shortend by creating a new lemma 'prime test' or 'probably prime test' or similiar. Does any body know a reference for the strong prime test?
I find the style of the proof a bit colloquial, it should be cleared up.
An alternative proof is the following:
Let S be the set {1,2,.., p-1} multiplication with a mod p induces a permution on S. Hence their products are equal,
1*2*..*(p-1)= (a*1)*(a*2)*...*(a*(p-1)) mod p
Since p is prime, the product 1*2*..*p-1 can be divided out and the result follows.
While we're at it we might as well refer to Lagrange's theorem and be done with it.
the followign appeared on the help page, mysteriously:
"Fermat's Little Theorem from Dynamical Systems"
For any n we define in the interval (0,1) ->(0,1) ( ) closed
Tn(x) = FP(nx), x<1
Tn(x) = 1, x=1
FP: Fractional Part
Lemma 1: Let n be an integer greater than 1. The function Tn(x) has
n fixed points in (0,1).
Lemma 2: Let a and b be positive integers. Then for all x belognig
to (0,1):
Ta(Tb(x)) = Tab(x)
Using values a and p, we consider the p-periodic point of Ta.
These p-periodic points are fixed points of Ta iterated p times, which
is Ta^p. This has a^p fixed points. Of these, exactly a are fixed
points of Ta.
Since p is prime the rest of them have minimal period p under Ta.
This means that there are a^p-a points that have minimal period p.
Since each point with minimal period p lies in an orbit p, there are
(a^p-a)/p orbits of size p. Since this is an integer, we see that p
divides (a^p-a).
Contents |
[edit] Carmichael's theorem
Does anybody know what Carmichael's theorem (currently mentioned in this article with a red link and an external link to MathWorld) actually says, as a theorem? The "theorem" on MathWorld is tautologous (it says that a certain number Ni has a certain property Pi, but the site defines Ni as the smallest number such that Pi(Ni) holds). Or should we really link to (and hope for an article on) Carmichael's function (the function which assigns Ni to the parameter i), which would be worth discussing even in the absence of a theorem? -- Toby Bartels 20:44, 8 Aug 2004 (UTC)
Okay, I was trying to understand this, but either I'm confused or someone botched something...
The first equation presented is (with == for the congruence):
a^p==a(mod p)
which (without the modulo notation) is the same as:
(a^p-a)/p
The first equation works for the numerical examples further down.
The second equation presented is:
a^(p-1)==1(mod p)
which is the same as:
(a^(p-1)-1)/p
The second equation fails to work for the numerical examples further down.
But after presenting the second equation, the the article expresses a third equation verbally, but not algebraically:
(a^(p-1))/p "will leave a remainder of 1 when divided by p."
In modulo notation, this would be the same as:
a^(p-1)==0(mod p)
The third equation works for the numerical examples further down.
I see two problems:
1) There is a difference between the second and third equations, but the switch from the second to third equation isn't obvious to the reader. This is because the third equation is only presented to the reader verbally and not algebraically as the other two were.
2) There is a leap of logic. How is it determined that the third equation validly returns one for numbers non-factorable by the tested prime? Is that by definition? Is that the statement of the theorem?
Am I confused or is this unclear?
Back again, I think I see the problem. It is with the second equation. Someone used congruence instead of equality, perhaps?
a^(p-1)==1(mod p)
but meant:
a^(p-1)=1(mod p)
I think it's supposed to be a normal equal sign, not the three line equal or congruence. Someone who knows for sure needs to check and correct. Thanks.
shouldn't it be "if p is any prime number or 1" given than 1 is not prime, and the theorem hold true for 1.
[edit] a & p coprime?
Hi, I've noticed that you've stated that Fermat's little theorem can be written most gernerally as (a^p) congruent to a (mod p), where p is prime and a ANY integer. I didn't think this was the theorem. I thought the theorem was the more general case where (a^p-1) is congruent to 1 (mod p) which is clearly not the case when p|a, as (a^p-1) will always be congruent to 0 (mod p). Blinded by my assumption here I reverted an example of the theorem involving the case a=6 & p=3, assuming it to be incorrect. I assume therefore that I was incorrect to revert the example on the basis of it being valid for the more general result as stated first.--Boris Allen 14:17, 12 February 2007 (UTC)
[edit] Hannam's lemma
I can't find any information on the existence of this lemma. It is an easy corollary of Wilson's theorem, though. -- Andareed (talk) 05:40, 9 December 2007 (UTC)
- It was the only edit by an IP.[1] That's often a bad sign. I think it should just be removed now. PrimeHunter (talk) 15:19, 9 December 2007 (UTC)
- I have removed it.[2] PrimeHunter (talk) 01:26, 3 January 2008 (UTC)
[edit] First uses
The sentence
The term "Fermat's Little Theorem" was first used in 1913 in Zahlentheorie by Kurt Hensel
seems to be contradicted by the quotation from Hensel given to support the claim. If as Hensel says the theorem "is customarily called" Fermat's Little Theorem, then Hensel was surely not the first to use the term.
It would be less confusing, perhaps, to say something like
The term "Fermat's Little Theorem" is attested as early as 1913 in Kurt Hensel's Zahlentheorie:
or
The first known published use of the term "Fermat's Little Theorem" is in Kurt Hensel's Zahlentheorie of 1913:
The mention of the earliest known English attestation is similarly incautious.
C.M.Sperberg-McQueen (talk) 15:14, 2 January 2008 (UTC)
