pseudo-primality and test of Solovay-Strassen

Question

Let $n$ be an odd integer, we say that $n$ is $a$-pseudoprime if $gcd(a,n)=1$ and :

$$\begin{pmatrix}\frac{a}{n}\end{pmatrix}=a^{\frac{n-1}{2}}\text{ mod } n $$

Euler's criterion states that if $n$ is not prime, then at most half of the elements $a$ in $\frac{\mathbb{Z}}{n\mathbb{Z}}^*$ are such that $n$ is $a$-pseudoprime.

Now I would like to know if we can have a better estimate for this (at least in some cases). For instance it can be shown that for $n:=p^{\alpha}$ there are exactly $p-1$ elements $a$ in $\frac{\mathbb{Z}}{n\mathbb{Z}}^*$ are such that $n$ is $a$-pseudoprime. To do this one should use the fact that $\frac{\mathbb{Z}}{p^{\alpha}\mathbb{Z}}^*$ is cyclic.

Actually the set of $a$ such that $n$ is $a$-pseudoprime is in this case exactly the set

$$\{a\mid a^{\frac{n-1}{2}}=\pm 1\text{ mod } n\}$$

My question is the following, do we have other cases (i.e. other $n$) where we can give a good estimate of the number of $a$'s such that $n$ is $a$-pseudoprime ?

I don't expect a general formula but if we assume $n$ square-free or even a Carmichael number I think it is possible to work this out.

Answer 1

If you know the prime factorization of $n=p_1 ^{d_1} \dots p_N ^{d_N}$, then the question has already been asked and answered: the number you are looking for is $\prod \limits _{k=1} ^N \gcd (n-1, p_k -1)$.

If you do not know the factorization of $n$, then Pomerance has obtained a lower bound given by $\exp (\log x) ^{\frac E {E+1} - \varepsilon}$ (see section 4) and an upper bound given by $\frac x {\sqrt {\exp \frac {\log x \log \log \log x} {\log \log x}}}$. These results are also cited by Erdős in an article from 1988. (While consulting them, keep in mind that $\log = \log _2$ and that in Pomerance's second article $\log_2 = \log \log$ and $\log_3 = \log \log \log$, a very uninspired notation. These estimates, though, are probably not what you have in mind for your students.)

Answer 2

The formula given in Alex M.'s answer is correct for pseudoprimes, but the question was asking about Euler-Jacobi pseudoprimes. For Euler-Jacobi pseudoprimes, the counting formula for odd $n$ is $E(n)=\delta(n)e(n)$ where:

$$\nu(n)=\min_{p|n} v_2(p-1)$$

$$e(n) = \prod_{p|n} \left(\frac{n-1}{2}, p-1\right)$$

$$\delta(n) = \left\{\begin{array}{ll} 2 & \text{if}\ \nu(n)=v_2(n-1) \\ 1/2 & \text{if}\ \exists p|n\ \text{with}\ v_2(p-1)<v_2(n-1)\ \text{and}\ v_p(n)\ \text{odd} \\ 1 & otherwise \\ \end{array}\right.$$

and $v_p(x)$ is the exponent of $p$ in the prime factorization of $x$. This formula was originally published in 1980 by Monier. Erdős and Pomerance give a nice presentation of the formula along with those for ordinary pseudoprimes and strong pseudoprimes. They use them to find counting formulas for the number of pseudoprimes.