Pseudo-Prime Bases

[a1call]

Hi all,
Is there a systematic method (other than brute force) to find a base whereby a given composite n will yield a false positive in FLT testing, other than n+1 and n-1 ?

Does such a base exist for any given composite?

Are such Bases finite in number?

Thank you in advance.

[axn]

Originally Posted by a1call

Does such a base exist for any given composite?

Excluding even numbers and powers of 3, the answer seem to be yes.

[a1call]

Thank you for the insight axn.

Re: My 2nd question, well it certainly can't be infinite unless bases greater than n are considered. So a mute question I can see.

[CRGreathouse]

Does "FLT testing" mean the Fermat probable-prime test? I'll assume this below, otherwise please clarify the term.

Originally Posted by a1call

Is there a systematic method (other than brute force) to find a base whereby a given composite n will yield a false positive in FLT testing, other than n+1 and n-1 ?

I don't know of one offhand, but I expect there is a method, at least if you have the factorization of n.

Originally Posted by a1call

Does such a base exist for any given composite?

If
\[n = p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}\]
(with p1 < p2 < ... < pk and all exponents positive integers) then there are
\[\prod_{i=1}^k \gcd(p_i-1, n-1)\]
bases to which n is a pseudoprime. This fits axn's comment pretty well: it's easy to see that only prime powers could have the minimum 2 bases, and p - 1 divides p^e - 1 so only powers of 3 work.

Originally Posted by a1call

Are such Bases finite in number?

As you pointed out, this question is moot -- there are only finitely many choices unless you count integers rather than integers mod n.