# Non existence of absolute euler pseudoprimes

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?

• 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. – Gerry Myerson Jun 14 '15 at 11:37
• The relevant paper might be, A fast Monte-Carlo test for primality, SIAM J Comput 6 (1977) 84-85. – Gerry Myerson Jun 14 '15 at 11:43