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