How to prove: EVERY strong pseudoprime is a Euler pseudoprime? I know when $n \equiv 3 \bmod 4$, the Euler pseudo prime is a strong pseudoprime, and that strong pseudoprime is a Euler pseudoprime.
But I don't know how to prove that every strong pseudoprime is a Euler pseudoprime.
I think that if we can prove that "if  $n \equiv 1 \bmod 4$, the strong pseudoprime is a Euler pseudoprime." 
Anyway I want to know how to prove [the question in the] title.
Thank you.
 A: When someone says that $n$ is an "Euler pseudoprime" to base $a$, they might mean one of two things.
Some authors mean simply $a^{n-1}\equiv \pm 1\mod n$.  If that's what you mean, then the commenters are correct: just check the definitions.  But that's probably not what you mean because this isn't equivalent to strong pseudoprime-ness.
Other authors mean $a^{n-1}\equiv \left(\frac{a}{n}\right)\mod n$.  (This is sometimes referred to as an Euler-Jacobi pseudoprime.)  I'm guessing you mean this because you refer to the $n\equiv 3(4)$ case of EJ PSPs and strong PSPs being the same.  The $n\equiv 1(4)$ case is trickier.  See the discussion starting on page 1009 of Pomerance, Selfridge, and Wagstaff's 1980 paper.
A: “Pseudoprime” means a^(n-1) = 1 modulo n. There is another property of primes that allows filtering out composites: If x^2 = 1 modulo n and n is prime then x = +/- 1.
Miller-Rabin uses this: Calculate a^(n-1) by raising a to an odd power, then squaring as often as needed. Miller-Rabin checks that none of the squarings produces a result of 1 mod n by squaring a number that isn’t +/- 1. Euler checks only that the last squaring doesn’t do this. So if you define Euler-Pseudoprimes like that then it filters out fewer composites and leaves more pseudoprimes than Miller-Rabin.
And if n = 3 mod 4, then n-1 is an odd number multiplied by 2^1, so Miller-Rabin has only one squaring to check, and Miller-Rabin and Euler test are absolutely identical in this case.
