Everybody knows the Fermat test : if n is a prime number then
a^{N} = a (mod N). Unfortunately, the reciprocal is false (for
example, 2^{341} = 2 (mod 341) and 341=31*11).

But, what can we say if a^{N} <> a (mod N) ?
Nothing, excepted that N isn't prime ? Not exactly. In fact, if
a^{N}= a^{i} (mod N) then, almost all the time, for N
sufficiently large, i will be a divisor of N and moreover, the quotient
N/i will be a pseudoprime to base a (so perhaps a prime number !). We can
generalize this result in order to have :

If b |

__Example :__ N=61687014991

We have
2^{61687014991}=128=2^{7} (mod 61687014991)

By the precedent
assertion, we have 61687014991 = 0 (mod 7) and 61687014991/7=8812430713 prime,
which can be easily verified !

This method could be used in order to find divisors smaller than
log_{b}(N) because r<N. So smaller values of b give better results
! (Note that the found divisor isn't necessarily prime)

I will publish later other various works about the Fermat rests (factorization, primality, frequencies of rests ...)