Every strong pseudoprime is an Euler-Jacobi pseudoprime to base $b$

Question

Prove that every strong (i.e. Miller-Rabin) pseudoprime to base $b$ is also an Euler-Jacobi pseudoprime to base $b$

I am trying to prove the above but I am struggling. Any hints?

Answer 1

This is Theorem $3$ in Section $3$ of this paper. The proof is very concise; I'm explaining it below in a little more detail.

Let $n$ be a positive integer. For a prime $p$, let $\nu_p(n)$ be the largest nonnegative integer $k$ such that $p^k\mid n$. For an integer $a$ with $(a,n)=1$, let $\operatorname{ord}_n(a)$ be the smallest positive integer $k$ such that $a^k\equiv 1\pmod{n}$.

If $p$ is prime, and $(a,p)=1$, then $\operatorname{ord}_p(a)$ divides $p-1$. Further, for any positive integer $k$, $\frac{\operatorname{ord}_{p^k}(a)}{\operatorname{ord}_p(a)}$ is a nonnegative power of $p$ (in particular, $\nu_2\big(\operatorname{ord}_{p^k}(a)\big)=\nu_2\big(\operatorname{ord}_{p}(a)\big)$ if $p\neq 2$). This follows from $$a\equiv 1\pmod{p^k}\implies a^p\equiv 1\pmod{p^{k+1}}$$ which, in turn, is obtained by expanding $a^p=(1+bp^k)^p$ and using $p\mid\binom{p}{j}$ for $0<j<p$.

Now let $n$ be a strong pseudoprime to base $b$; this means that $n$ is odd, $(b,n)=1$, and if we write $n=2^s d+1$ with $d$ odd, then either (i) $b^d\equiv 1\pmod{n}$ or (ii) $b^{2^r d}\equiv -1\pmod{n}$ for some $r$ with $0\leqslant r<s$. (Also, $n$ is composite, but we won't use it.) We have to prove that $n$ is an Euler-Jacobi pseudoprime, i.e. that $b^{(n-1)/2}\equiv\big(\frac{b}{n}\big)\pmod{n}$.

---

Observe that $v:=\nu_2\big(\operatorname{ord}_n(b)\big)$ is equal to $0$ in the case (i) and to $r+1$ in the case (ii), so that $$b^{(n-1)/2}\equiv -1\pmod{n}\quad\text{if }v=s;\\b^{(n-1)/2}\equiv 1\pmod{n}\quad\text{otherwise}.$$ Also, if $p\mid n$ and $m:=p^{\nu_p(n)}$, then $v=\nu_2\big(\operatorname{ord}_m(b)\big)$, hence $v=\nu_2\big(\operatorname{ord}_p(b)\big)$ as noted above.

Now let $n=p_1\cdots p_k$ be the prime factorization of $n$ (with the $p$'s not necessarily distinct).

Then $v\leqslant v_j:=\nu_2(p_j-1)$ for $1\leqslant j\leqslant k$; let $J$ be the set of indices $j$ with $v=v_j$. Since $p_j-1$ is $2^{v_j}$ times something odd, we have $$p_j\equiv 2^v+1\pmod{2^{v+1}}\quad\text{if }j\in J;\\p_j\equiv 1\pmod{2^{v+1}}\quad\text{otherwise}.$$

This gives $n\equiv(2^v+1)^{|J|}\pmod{2^{v+1}}$. That is, if $|J|$ is odd, then $n\equiv 2^v+1\pmod{2^{v+1}}$ and hence $(s=)\nu_2(n-1)=v$; otherwise, $n\equiv 1\pmod{2^{v+1}}$ and hence $s>v$. As noted above, this implies $$b^{(n-1)/2}\equiv(-1)^{|J|}\pmod{n}.$$

On the other hand, since $v=\nu_2\big(\operatorname{ord}_{p_j}(b)\big)$ for each $j$, we have $b^{(p_j-1)/2}\equiv -1\pmod{p_j}$ if and only if $v=v_j$. This gives $\big(\frac{b}{n}\big)=\prod_{j=1}^k\big(\frac{b}{p_j}\big)=(-1)^{|J|}$, finishing the proof.