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

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,

-
I think you have a typo: mod 34 should be mod 341. – Fixee Feb 28 '11 at 7:41
@Fixee: Thanks, fixed. – Chan Feb 28 '11 at 7:49
2^10x341 should be 2^10x34, right? – ypercube Feb 28 '11 at 12:26
@ypercube: you're right. Thanks, fixed. – Chan Mar 1 '11 at 0:56

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