1. ## Fermat Pseudoprime problem

Fermat test base a, $(a,N)=1 , \ \ a^{N-1} = 1 \ \ mod \ N$

problem is, how many values of a are necessary to determine the primality or compositeness of N < 1000000 excluding Carmichael numbers ?

i found, if we test with primes 2,3,5,7,11 and it will find all the primes < 1000000. so i guess we need to test at least 5 values of a?

this is actually a programming problem, and i dont think it is possible to answer without testing

2. You cannot determine it definitely. Even if you tested all values of $a$, it could still be composite. But the more values of $a$ you test, the higher the probability that it is prime.
I cannot find this information on the internet anymore, but I think the probability that the number is prime is equal to $1 - 10^{\frac{-k}{2}}$, where $k$ is the number of values of $a$ tested. I cannot guarantee this is the real probability formula, but it is something in this fashion.

3. ## pro

the problem is, the question asks to test with some a in range <1000000 excluding the carmichael. so the problem is to find out whether it is composite or prime. there is no probability of getting a carmichael becausee we remove it.

4. Try with 20 values of a. That should be good enough.

5. ## well

well, i tried 2,3,5,7,11 and it works. it gives all prime numbers...

6. Then everything's good, try to find the probability formula