Pseudo-Prime Bases
 

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.:smile:

[QUOTE=a1call;475929]Does such a base exist for any given composite? [/QUOTE]

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

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.:smile:

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

[QUOTE=a1call;475929]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 ?[/QUOTE]

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

[QUOTE=a1call;475929]Does such a base exist for any given composite?[/QUOTE]

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.

[QUOTE=a1call;475929]Are such Bases finite in number?[/QUOTE]

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