How could a negative Fermat test help us to find prime numbers ?



    Everybody knows the Fermat test : if n is a prime number then aN = a (mod N). Unfortunately, the reciprocal is false (for example, 2341 = 2 (mod 341) and 341=31*11).
    But, what can we say if aN <> a (mod N) ? Nothing, excepted that N isn't prime ? Not exactly. In fact, if aN= ai (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 bN = r (mod N)
and if we find a small i such that bi = r (mod N)
then i often divides N and if so, N/i will pass the Fermat test in base b.

Important : This is true for N sufficiently large


Example : N=61687014991
                We have 261687014991=128=27 (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 logb(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 ...)

Back to home page