1. ## Question about Carmichael number

Definition:
An absolute Fermat pseudoprime, also known as a Carmichael number, is a composite number which passes the Fermat test for any base a s.t.
(a,N) = 1.

Question:
How many values of a are necessary to determine the primality or compositeness of those N in the trial range $\displaystyle <10^6$
which are not absolute Fermat pseudoprimes?

2. Originally Posted by silversand
Definition:
An absolute Fermat pseudoprime, also known as a Carmichael number, is a composite number which passes the Fermat test for any base a s.t.
(a,N) = 1.

Question:
How many values of a are necessary to determine the primality or compositeness of those N in the trial range $\displaystyle <10^6$
which are not absolute Fermat pseudoprimes?
Since Carmichael numbers have a minimum of 3 factors, the cube root of 10^6 or about 100.

If you do NOT get a factor within that range, you can be sure that it is NOT a Carmichael number.

3. ## more

Originally Posted by aidan
Since Carmichael numbers have a minimum of 3 factors, the cube root of 10^6 or about 100.

If you do NOT get a factor within that range, you can be sure that it is NOT a Carmichael number.

still havent totally got it.

why did the question ask "how many values of a" ?

i tried to make a program like this,

Step 1: filter out those prime N by trial division, then filter those N with least prime factor > 100.

S2: find the GCD of all a from 2 to N-1 and each N.

S3: filter those a, with GCD > 1.

S4: find $\displaystyle a^{N-1} mod N$ with the rest of a .

if all of them =1 , then N is a carmichael.

i thought you mean, in S2, we only need to find GCD of all a from 2 to 100?
is that what you meant?