The Little Fermat Theorem states that if p is a prime then p divides ap-a, p not equal to a. After factoring : a(a(p-1)-1)
The converse of the theorem is not true, in fact there are composite numbers that divide ap-a. They are referred to as psuedoprimes.
The Fermat numbers denoted by: Fn are always primes or psuedoprimes when a=2.
22n+1 is the suspected prime to be tested.
Let a = 2 then: 2(22n+1)-2, or 2[222n-1] is divisible by 22n+1.
Let f = 22n, This is a number that only has 2 as its factor.
That leaves us with the expression 2f-1 to factor.
Using the fact that x2-y2 factors to (x+y)(x-y)
then 2f-1 factors to (2(f / 2)+1)(2(f / 2)-1)
Factoring the -1 factor repeatedly until the exponent is 1 we get:
2f-1 factors to (2(f / 2)+1)(2(f / 4)+1)(2(f / 8)+1)(2(f / 16)+1) . . . (22n+1) . . .(2+1)(2-1)
Example:223+1 is F3, or 28+1 and 28 = 256
Substituting all values in the original expression we get 2(2256-1) is divisible by 28+1.
Factoring: 2256-1 =(2128+1)(264+1)(232+1)(216+1)(28+1)(24+1)(22+1)(2+1)(2-1)
Fermat, the father of number theory, conjectured that all 22n+1 were prime. the first four are but 232+1 is composite. Euler proved that this number is divisible by 641. (more on all of this later)
I have played with this expression trying to find a pattern to psuedoprimes. I have found that if a has the pattern of kp+1 or (kp+1)t then any number p divides the expression: an-a.
The psuedoprime 341 works with a = 2. 2(2340-1) is divisible by 341. By changing to base 210. The expression becomes (2)[(210)34-1]. It then follows that 341 divides the expression because 210 = 1024 = 3(341)+1. The interesting aspect to this is that regardless of the power the expression is divisible by the psuedoprime. This is because the digits in that base are all kp.
(2)[(210)n-1] is divisible by 341.
X(p-1) - Y(p-1) = 0 mod(p) is another interesting fact proven by the Little Fermat Theorem.