# pseudo-primality and test of Solovay-Strassen

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.

## 2 Answers

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.)

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.