Talk:Fermat's little theorem

From Wikipedia, the free encyclopedia

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).

[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 N_i has a certain property P_i, but the site defines N_i as the smallest number such that P_i(N_i) holds). Or should we really link to (and hope for an article on) Carmichael's function (the function which assigns N_i 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)