TransWikia.com

Does $n$ divide $2^{n-1} - 1$ for an infinite number of composite $n$?

Mathematics Asked on January 14, 2021

Yes, $p$ always divides $2^{p-1}-1$ for any prime $p ge 3$. Are there any odd composite $n$ for which $n$ divides $2^{n-1}-1$?

And on a related note, $p$ never divides $2^{p-1}+1$ for any prime $p ge 3$. Are there any odd composite $n$ for which $n$ divides $2^{n-1}+1$?

I ask these questions because they are natural spin-offs from some well-known questions. It is well-known that no integer $n>2$ divides $2^n-1$. And it is basic to establish $p$ always divides $2^{p-1}-1$ for any prime $p ge 3$. But for general $n$, the relationship between the integers $varphi(n)$ and $n-1$ is not clear-cut.

Thanks for considering!

One Answer

The answer to your first question is yes.

If a composite integer $n$ divides $ 2^{n−1} − 1$, then $n$ is called a Fermat pseudoprime to base $2$.

There are infinitely many.

You could see some in the The On-Line Encyclopedia of Integer Sequences.

Answered by J. W. Tanner on January 14, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP