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

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?

• $2^{4-1} = 8 = 4\times 2$
– MBW
Commented Jun 7, 2020 at 17:56
• $n=4$ implies that $2^3=4\times a$. Thus, $a=2$, and $n=4$ is not prime. Commented Jun 7, 2020 at 17:56
• Generally speaking, to disprove something, all you need to do is find one counterexample. In this case, all that that requires is picking an $n$ that doesn't work. Commented Jun 7, 2020 at 17:57
• These counterexamples are called Fermat pseudoprimes base 2. The smallest example is $n=11\cdot 31=341$. Commented Jun 7, 2020 at 17:58

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