Fermat, while working on the properties of Mersenne numbers, M(n)=2^n-1,
observed a pattern in exponents that are powers of 2:

M( 2) = 3
M( 4) = 3 * 5
M( 8) = 3 * 5 * 17
M(16) = 3 * 5 * 17 * 257
M(32) = 3 * 5 * 17 * 257 * 65537
M(64) = 3 * 5 * 17 * 257 * 65537 * 4294967297
         ....

which is actually a repeated application of the difference of squares identity:

 2^2-1 = (2^1-1)(2^1+1) = (2^1+1)
 2^4-1 = (2^2-1)(2^2+1) = (2^1+1)(2^2+1)
 2^8-1 = (2^4-1)(2^4+1) = (2^1+1)(2^2+1)(2^4+1)
2^16-1 = (2^8-1)(2^8+1) = (2^1+1)(2^2+1)(2^4+1)(2^8+1)
         ....
2^2^(m+1)-1 = (2^1+1)(2^2+1)(2^4+1)(2^8+1)...(2^2^m+1)

Fermat numbers
F(m)=2^(2^m)+1
(MathWorld)(Wikipedia)

F(0) =  2^1+1 = 3
F(1) =  2^2+1 = 5
F(2) =  2^4+1 = 17
F(3) =  2^8+1 = 257
F(4) = 2^16+1 = 65537
F(5) = 2^32+1 = 4294967297           (10 digits)
F(6) = 2^64+1 = 18446744073709551617 (20 digits)
        ....


We can rewrite the last identity as:

F(m+1)-2=F(0)F(1)F(2)F(3)...F(m)

Thus, any two distinct Fermat numbers are coprime. 

Fermat must have known this fact from the properties of Mersenne numbers. [Did he?]


Now, using the above identity, we have:

2^(F(m)-1) = 2^2^2^m = F(2^m)-1 = F(0)F(1)F(2)...F(m)...F(2^m-1) +2 -1 ≡ 1 (mod F(m))

Thus, each F(m) is a base-2 probable prime.


Did Fermat know this last result?
Because if he had known, that would have been a good justification for his
  "worst-ever conjectue in the history of mathematics"
   
     All the numbers of the form 2^2^m+1 are prime

                    In fact
          F(0), F(1), F(2), F(3) and F(4)
             are THE only primes
             we have found so far.


Quote from Knuth:
The art of computer programming, vol. 2, 4.5.4, p.391

Fermat once verified that the numbers 2^1+1, 2^2+1, 2^4+1, 2^8+1, and 2^16+1 are prime.
In a letter to Mersenne written in 1640, Fermat conjectured that 2^2^m+1 is always prime,
but said he was unable to determine definitely whether the number 4294967297 = 2^32+1
is prime or not. Neither Fermat nor Mersenne ever resolved this problem,
 although they could have done it as follows:
The number 3^2^32 mod (2^32+1) can be computed by doing 32 
operations of squaring modulo 2^32+1, and the answer is 3029026160;
therefore (by Fermat's own theorem, which he discovered in the same year 1640!)
the number 2^32+1 is not prime.

(3^2^32 ≡ 3029026160 (mod F5))
5^2^32 ≡ 2179108346 (mod F5)
[PARI][perl]

Maybe Fermat did the clculation in base 2 and saw that the result was 1
But he definitely didn't do it in base 3! [Who did? 1877 Pepin?] 




(OEIS A023394) Prime factors of Fermat numbers
factors sorted by k
factors sorted by size
factors sorted by date

Wilfrid's (Fermat factoring status)

Luigi & Leonid's (FermatSearch project)

Catherine Cowie's
 (history notes)
 (Pepin)

Gary Gostin and Catherine Cowie's (cofact)