Exercise 2.4.11 (Generalization of the method of factorization)

Proof. If $m-1=2^{j}d$, where $2\nmid d$, since $m$ is not a spsp( $a$), $a^d=a^{(m-1)∕2^j}\not\equiv 1$. Since $m$ is a pseudoprime to the base $a$, $a^{m-1}\equiv 1(\mathit{mod}m)$.

If $i$ is the greatest $l$ such that $a^{(m-1)∕2^l}\equiv 1(\mathit{mod}m)$ (such an integer $i$ exists by the preceding remarks), then

( $a^{(m-1)∕2^{i+1}}\not\equiv 1(\mathit{mod}m)$ by maximality of $i$, and $a^{(m-1)∕2^{i+1}}\not\equiv -1(\mathit{mod}m)$, otherwise $m$ would be a spsp( $a$).)

Let $x=a^{(m-1)∕2^{i+1}}$. Then $x^2\equiv 1(\mathit{mod}m)$ and $x\not\equiv \pm 1(\mathit{mod}m)$. Then Problem $9$ shows that $(x-1)\wedge m$ and $(x+1)\wedge m$ are non trivial divisors of $m$.

If $r,1\le r<m$, is such that $x=a^{(m-1)∕2^{i+1}}\equiv r(\mathit{mod}m)$, then $x=r+\mathit{km}$, so $\delta =(x-1)\wedge m=(r-1+\mathit{km})\wedge m=(r-1)\wedge m$, given by the Euclidean algorithm, provides a non trivial divisor of $m$ (and also $(r+1)\wedge m$). □