I want to find all bases for which 39 (say) is an Euler-Jacobi pseudoprime, i. e. numbers $b$ prime to 39 s.t.
$b^\frac{n-1}2\equiv \left(\frac bn\right) \mod n$
The trivial bases are $1$ and $38$ but how can I check the remaining numbers efficiently? Is there a trick?