Waste less time on Facebook — follow Brilliant.

A good problem

This is a problem I recently found which I could not solve. This was there in a book prescribed for RMO and INMO. Here it is:

Determine with proof the set of all positive integers \(n\) such that \(2^n +1\) is divisible by \(n^2\).

Any hint, or solutions are welcome

Note by Rakhi Bhattacharyya
1 year ago

No vote yet
1 vote


Sort by:

Top Newest

This is IMO 1990 P3. See here. Ameya Daigavane · 1 year ago

Log in to reply

Since, \(2^{n} +1\) is divisible by \(n^2\).

\(2^{n}+1= kn^2\)
\(\implies 2^n = (\sqrt{k}n+1)(\sqrt{k}n-1)\)
Let, \(\sqrt{k}n-1 = a\)
\(2^n = (a)(a+2)\)
We have \(2\) powers of \(2\) with a difference of \(2\);that add up to an integer value;
Which, must be \(2\) and \(4\)
Hence, \(n=3\) and \(k=1\) is one answer.

Moreover, as @Kushagra Sahni has pointed out; \(n=1\) also works. I cant find a rigorous proof approach to \(n=1\) so, for now I will be satisfied by the fact that since 1 divides every natural number it divides \(2^n +1\).

P,S.: I am not very good at these kind of proofs so, there may be a trick or two I have missed and maybe even another value for \(n\) (though, I somehow feel quite sure about this answer.) Yatin Khanna · 1 year ago

Log in to reply

@Yatin Khanna Thanks for putting in the effort to write up the solution. Unfortunately, it is incorrect because of:

  1. You are making the assumption that \( k\) must be a perfect square, so that \( \sqrt{k} n - 1 = a \) is an integer.

Keep up the good effort! Practice makes perfect Calvin Lin Staff · 11 months, 3 weeks ago

Log in to reply

@Yatin Khanna How do you know \( a \) is an integer? Ameya Daigavane · 1 year ago

Log in to reply

@Yatin Khanna n=1 is also an answer. Put k=9. U believe these are the only 2 solutions. Kushagra Sahni · 1 year ago

Log in to reply

@Kushagra Sahni Told you I tend to miss few tricks...
\(k=3\) and \(n=1\) also works. Yatin Khanna · 1 year ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...