2
$\begingroup$

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.

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

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.

$\endgroup$
  • $\begingroup$ Please give a sample for any case $<341.$ $\endgroup$ – Leox May 18 '15 at 20:37
  • 1
    $\begingroup$ 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$ $\endgroup$ – Ross Millikan May 18 '15 at 20:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.