3
$\begingroup$

Possible Duplicate:
How many rationals of the form $\large \frac{2^n+1}{n^2}$ are integers?

A friend of mine asked me this question over lunch, and it's been a week that I can't do research... This is a riddle that he made up, so we actually don't know if this is even solvable.

The question is stated in the title:

For what values of $n\in\mathbb{Z}$ does $n^2$ divide $2^n+1$?

The answer, I'm 99.9% sure is only $n=1$ or $n=3$ (I verified that for $n$ up to $\sim 10^6$).

Here's how I tried to attack that: Clearly, $n$ must be odd. Let's denote by $k$ the order of $2$ mod $n^2$. Since $2^n=-1$, we know that $k$ does not divide $n$, but divides $2n$. Therefore $k=2d$, where $d|n$. We also know that $k|\phi(n^2)=n\phi(n)$ but that is automatically satisfied if $\phi(n)$ is even, and that's always true. Don't know if this is a good direction...

Any other ideas?

  • 1
    This is an International Math Olympiad problem I believe. And possibly a dupe. Found it!2012-03-08

0 Answers 0