When is $\frac{2^n+1}{n^2}$ an integer?

Question

Can anyone see how to solve this number puzzle?

Find all integers $n>1$ such that

$$\frac{2^n+1}{n^2}$$ is an integer.

@WillJagy An old math puzzle book I am afraid which doesn't have answers. — , Apr 15 '13 at 20:04

score 5 · Accepted Answer · edited Apr 15 '13 at 20:27

5

Hint: Since this problem comes from number theory, then I suggest you to look at equivalent congruence problem

$$ 2^n+1=k n^2 \implies 2^n \equiv -1\pmod{n^2} .$$

edited Apr 15 '13 at 20:27

Marc van Leeuwen

answered Apr 15 '13 at 20:09

Mhenni Benghorbal

Oh, thanks. The solution there isn't that simple! – Apr 15 '13 at 20:18
@motl737: You are lucky. The whole idea was to shift the equivalent congruence form then look for the solution. – Mhenni Benghorbal Apr 15 '13 at 20:20

score 1 · Answer 2 · edited Apr 13 '17 at 12:21

1

edited Apr 13 '17 at 12:21

Community

answered Apr 15 '13 at 20:36

Alex L

2 Answers2