Showing that an integer is a strong pseudoprime

Question

I need to show that $n=1,373,653$ is a strong pseudoprime to the bases 2 and 3. I've used Fermat's Little Theorem on the prime decomposition of $n=829\cdot1657$ to get $$2^{828}\equiv1\ mod\ 829\quad, 2^{1656}\equiv1\ mod\ 1657\quad, 3^{828}\equiv1\ mod\ 829\quad, and\quad 3^{1656}\equiv1\ mod\ 1657$$ I am trying to use the Chinese remainder theorem to multiply the moduli together to get what I need to show but I am stuck at this point. Any advice would be greatly appreciated

Answer 1

Let $n=1373652$. Note that $n-1=1373652=4\cdot 343413$. You want to show that if $a$ is $2$ or $3$, then either $a^{343413}\equiv 1\pmod n$ or one of $a^{343413}$ or $a^{686826}$ is $\equiv -1\pmod{n}$.

Let us check that $2^{686826}\equiv -1\pmod{829}$. Equivalently, we want to show that $2^{414}\equiv -1\pmod{829}$. This follows from the fact that $2$ is a quadratic non-residue of $829$.

You still need to deal with $a=3$.