Giving a counterexample to $ 2^{n-1}- 1 = n \cdot a \iff n \text{ is prime}$

Question

Fermat's little theorem asserts: $ n \text{ is prime} \implies 2^{n-1}- 1 = n \cdot a $.

However , the converse , $ 2^{n-1}- 1 = n \cdot a \implies n$ is prime, is not true . How can we prove it , taking odd $n$ (without using a computer)?

Edit: I know that $341$ works , but how can I prove it's a counterexample without using a computer?

Answer 1

As commented by hardmath, you are looking for pseudoprimes base $2$, and $341$ is a counterexample. To prove it without using a computer, note that $2^{5}=32=31+1\equiv1\bmod31$ and $2^5=32=33-1\equiv-1\bmod11$, so $2^{10}\equiv1\bmod31$ and $11$ and therefore $\bmod 341$, so $2^{340}\equiv1\bmod341$.

Answer 2

Look up Carmichael numbers. The smallest Carmichael number is $n=561=3\cdot 11\cdot 17$ and it satisfies $$b^{n-1}\equiv 1\pmod{n}$$ for all $b$ such that $b$ is relatively prime to $561.$

Answer 3

Simple: prove that $2^{340} \equiv1 \pmod{341}$

We have $341=11\cdot31 \implies \phi(341) =300$ and by euler's theorem, $$2^{300} \equiv1 \pmod{341}$$ Now, $2^{40} \equiv 1024^4 \equiv1^4 \equiv1\pmod{341}$ and multiplying the two congruences we get the required result