Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How can one find all positive integers $n$ for which $n \mid 2^{n-1}+1$?

share|improve this question
3  
Two Hints: for even $n$, $2^{n-1}+1$ is odd; for odd primes $p$, $p|2^{p-1}-1$ by Fermat's little theorem. –  Henry Apr 9 '11 at 12:12

2 Answers 2

The idea behind this solution is that if $n>1$ then $n$ must be odd, so $2^{n-1}+1$ is a sum of coprime squares, and we get $n\equiv 1 \bmod{4}$, so that $2^{n-1}+1$ is a sum of coprime fourth powers and $n\equiv 1 \bmod{8}$, etc...

We claim that if $p$ is an odd prime such that $p\mid x^{2^k}+1$ for some natural $k$ and integer $x$, then $p\equiv 1 \bmod{2^{k+1}}$. Because $p\mid x^{2^k}+1$ implies that $x^{2^{k+1}}\equiv 1 \bmod{p}$ and $x^{2^k}\equiv -1 \not \equiv 1 \bmod{p}$, then the order of $x$ modulo $p$ divides $2^{k+1}$ and doesn't divide $2^k$. We conclude that it's $2^{k+1}$, and using Fermat's little theorem we get that $2^{k+1}\mid p-1$, as we wanted.

Back to the original problem, we claim that $n=1$ is the only solution. It's clearly a solution so suppose that $n>1$. Then $n$ is necessarily odd, so let $k$ be the greatest integer such that $n\equiv 1 \bmod{2^k}$. Using the lemma proved before with $x=2^{\frac{n-1}{2^k}}$, we get that all prime factors of $n$ must be $1\bmod{2^{k+1}}$ (because they're odd). This immediately implies that $n\equiv 1 \bmod{2^{k+1}}$, contradicting the maximality of $k$, as desired.

share|improve this answer

$If\ n|(2^{n-1}+1)$

Clearly, n is odd.

$2^{n-1}≡-1\pmod{n}$

$2^{2(n-1)}≡1\pmod{n}$

=> $\mathrm{ord}_n2|2(n-1)$, but $\mathrm{ord}_n2∤(n-1)$ and $\mathrm{ord}_n2∤2$ as n-1 is even.

=>$\mathrm{ord}_n2=2(n-1)$ which is impossible as $\mathrm{ord}_n2$ must divide $\phi(n) ≤ n-1 $

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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