<s>[INST] Strong Pseudoprime to base square? Question:

Let n>1 be an odd composite integer and let a be an integer with (a,n)=1.
Show that, if n is a strong pseudoprime to base a, then n is also a strong pseudoprime to base $a^2$

What I have done is that : let $n-1=2^{s}t$ then assumption implies that
$1. a^t \equiv 1 \pmod n$ or
$a^t \equiv -1 \pmod n$ or
$2.a^{2t} \equiv -1 \pmod n$
or... $a^{2^{s-1}t} \equiv -1 \pmod n$
so by part 1, $a^{2t} \equiv 1 \pmod n$ or
by part 2, $a^{2t} \equiv -1 \pmod n$
or... $a^{2^{s-1}t} \equiv -1 \pmod n$
these two results means that $n$ is strong pseudoprime to base $a^2$
when(if) we have also that $a^{2^{s}t} \equiv -1 \pmod n$
but the last term always be false because $a^{2^{s}t} \equiv a^{n-1}\equiv 1 \pmod n$ by that (strong pseudoprime is fermat pseudoprime) so we don't need that $a^{2^{s}t} \equiv -1 \pmod n$
so n is also a strong pseudoprime to base $a^2$ .. is my opinion right?
 [/INST] Yes, the strong pseudoprime test doesn't require that you test $a^{n-1} \equiv 1 \bmod n$, but in any case that also works. Your proof basically works OK but gets a little unclear, perhaps because of the confusion between $a^{2k}$ and $(a^2)^k$.
So to restate the strong pseudoprime rule:

Define $t,d$ with $t\cdot 2^d = n-1$ with $t$ odd.  $n$ is a pseudoprime base $a$ if either:

*

*$a^t \equiv 1 \pmod n$


*$a^{t\cdot2^k} \equiv -1 \pmod n$ for some $0 \le k \le (d-1)$

Note that these conditions also assure that $a^{n-1} \equiv 1 \pmod n$ without further evaluation.
Now we assume that $a$ meets one of these conditions, and check that $b= a^2$ also meets them:

*

*$a^t \equiv 1 \pmod n \implies  b^t = a^{2t} \equiv 1 \pmod n $ (condition 1 applies for $b$)


*$a^t = a^{t\cdot2^0} \equiv -1 \pmod n \implies  b^t = a^{2t} \equiv 1 \pmod n $ (condition 1 applies for $b$)


*$a^{t\cdot2^k} \equiv -1 \pmod n$ for some $1 \le k \le (d-1) \implies  b^{t\cdot2^(k-1)} = a^{t\cdot2^k} \equiv -1 \pmod n$ (condition 2 applies for $b$)
Hence $n$ is also a strong pseudoprime base $b=a^2$.
</s>