Given an odd integer n ≥ 5, and a base 2 ≤ a ≤ n-2, $a^{n-1} = 1 \mod n$ whenever n is a prime, and whenever the result is not 1, n is composite. Plus composite numbers where the result is 1 are rare. A composite number passing this test is a "pseudo-prime" or "Fermat pseudo-prime". There are slightly more clever tests producing "Euler pseudo-primes" or "Miller-Rabin pseudo-primes".
I have always been told that one should take a prime number a as the basis in these tests, not a composite number. And it is easy to show that taking a square $a^2$ gives weaker results. However, I tried to find sets of three bases where the smallest number that is a pseudo-prime to all three bases is as large as possible, and composite numbers seem to give good results, for example there is no $n < 2^{32}$ that is a Rabin-Miller pseudo-prime to bases 13, 18 and 35.
Question: Is there a reason to avoid composite numbers as bases when testing whether numbers are pseudo-primes to multiple bases or is that just folklore? Should we avoid bases with common divisors?
BTW. 25,326,001 is a Miller-Rabin pseudoprime to bases 2, 3 and 5, so that's at least 180 times worse than 13, 18 and 35.
There is no need to choose primes as bases. Some composites are even better than primes: there are 19322 strong pseudoprimes with bases 2 and 3 below $10^{15}$ but only 14623 with bases 2 and 15. The results are similiar with several multiples of 15, e. g. 1215 and 735.
15283202437 is the lowest strong pseudoprime with bases 2, 453 and 735; $453 = 3 \cdot 151,\ 735 = 3 \cdot 5 \cdot 7^2$.
Strong pseudoprimes base $a$ are composite numbers that pass the Miller-Rabin test base $a$.