3
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.