A natural number $n$ is called an Euler pseudoprime(sometimes Euler-Jacobi pseudoprime) wrt to $a$ iff $$a^{(\frac{n-1}2)} \equiv \Big(\frac an\Big) \pmod n$$ where $\Big(\frac an\Big)$ is the Legendre symbol.

$n$ is called an absolute Euler pseudoprime if it is a pseudoprime with respect to all $a , \text{gcd}(a,n)=1$. I want to prove that absolute Euler pseudoprimes don't exist.

It is clear that they must be a subset of Carmichael numbers. Let $n=p_1p_2\dots p_k$. I will also be done if I can prove that there exists $p_i, 2(p_i-1) \nmid (n-p_i).$ This seems a little messy though, is there a more elegant approach?

  • $\begingroup$ en.wikipedia.org/wiki/Euler–Jacobi_pseudoprime says, "There are no numbers which are Euler–Jacobi pseudoprimes to all bases as Carmichael numbers are. Solovay and Strassen showed that for every composite $n$, for at least $n/2$ bases less than $n$, $n$ is not an Euler–Jacobi pseudoprime." They don't give a reference, but there can't be too many papers written by Solovay and Strassen. $\endgroup$ – Gerry Myerson Jun 14 '15 at 11:37
  • $\begingroup$ The relevant paper might be, A fast Monte-Carlo test for primality, SIAM J Comput 6 (1977) 84-85. $\endgroup$ – Gerry Myerson Jun 14 '15 at 11:43

There are many online resources analyzing the Solovay-Strassen algorithm. For example, there is a nice bachelor's project (!) explaining the common primality tests by Monica Perrenoud. You want Theorem 6.4 on page 26.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.