Is $2^{340} - 1 \equiv 1 \pmod{341} $?

Question

Is $2^{340} - 1 \equiv 1 \pmod{341} $?

This is one of my homework problem, prove the statement above. However, I believe it is wrong. Since $2^{10} \equiv 1 \pmod{341}$, so $2^{10 \times 34} \equiv 1 \pmod{341}$ which implies $2^{340} - 1 \equiv 0 \pmod{341}$

Any idea?

Thanks,

Answer 1

What you wrote is correct. $$2^{340}\equiv 1\pmod {341}$$ This is smallest example of a pseudoprime to the base two. See Fermat Pseudo Prime.

Answer 2

HINT $\rm\ \ 2^{340}\equiv 2\ \ (mod\ 11\cdot31)\ \Rightarrow\ mod\ 11\::\ 2^{339}\equiv 1\equiv 2^{10}\ \Rightarrow\ 2^{gcd(339,10)} \equiv 1\:,\:$ i.e. $\ 2\equiv 1\ \Rightarrow\Leftarrow$