How to prove: EVERY strong pseudoprime is a Euler pseudoprime?

Question

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.

Answer 1

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.

Answer 2

“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.