Can you provide a proof or counterexample to the following claim ?

Let $p$ be a prime number greater than two then :

$$2^{2^{p-1}-1} \equiv 1 \pmod{2^p-1}$$

Pari/GP implementation .

I have tested this claim up to $5 \cdot 10^4$ .

I was searching for a counterexample using the following Pari/GP code :

  • $\begingroup$ Yes, that finds primes, but it also finds Fermat pseudoprimes to base 2, also called Sarrus numbers or Poulet numbers. A001567, eg 341, 561, 645, 1105, 1387, 1729 $\endgroup$ – PM 2Ring Jan 18 '18 at 10:32

From Fermat's little theorem we know that $p\mid 2^{p-1}-1$ which means that $2^{p-1}-1=k\cdot p$.
Then, $2^{2^{p-1}-1}-1=2^{kp}-1=(2^p)^k-1=(2^p-1)(2^{p(k-1)}+2^{p(k-1)}+\ldots+1)$ which is a multiple of $2^p-1$ which is equivalent to what you ask.


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.