4
$\begingroup$

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,

  • 0
    You are right. Looks like your homework had a typo. It was probably intended to say $2^{340}-1\equiv 0\pmod {341}$.... Leibnitz asserted that if n>1 and $2^n\equiv 1\pmod n$ then $n$ is prime but later admitted he was mistaken, I haven't checked but I think $n=341$ is the least counterexample.2017-10-01

2 Answers 2

5

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.

  • 0
    Thanks for the confirmation as well as the information about Fermat Pseudo Prime.2011-02-28
0

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$