# Find the first Poulet number

A Poulet number (OEIS $A001567$) is called a composite number $n$ such that $2^{n-1}−1$ is divisible by $n$. The first such a numbers are: $$341, 561, 645, 1105, \ldots$$ Question: How to prove that $341=11 \cdot 31$ is the fist Poulet number and there are not any another such a number which is less than $341$?

Of cource, it is easy to show by direct calculation in any computer system but I hope it can be proved by elementary numbers tools.

• Hint: Proving this is the same as proving that $341$ is the smallest base-2 Fermat pseudoprime. – Prasun Biswas May 18 '15 at 20:20
• I know that that is the same numbers but how to prove it? – Leox May 18 '15 at 20:26

Showing that $2^{340} - 1$ is divisible by $341$ is routine. Showing that $2^{n-1} - 1$ is not divisible by $n$ for any odd composite $< 341$ would appear to require looking at a lot of cases one by one. It is all "elementary" but will take some time by hand.
• Please give a sample for any case $<341.$ – Leox May 18 '15 at 20:37
• One sample is to ask if $15$ divides $2^{14}-1=16383$ It does not. In general $3$ divides $2^{2k}-1$ and does not divide $2^{2k+1}-1$, so if $3$ is a factor of $n$, then $n$ must be even. This will eliminate a fair number of potential $n$ less than $341$ – Ross Millikan May 18 '15 at 20:42