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 Jacobi 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?
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.