Try this beautiful problem from American Invitational Mathematics Examination, HANOI, 2018 based on Divisibility.

Divisibility – HANOI 2018


Find all positive integers k such that there exists a positive integer n, for which \(2^{n}+11\) is divisible by \(2^{k}-1\).

  • is 2, 4
  • is 2, 0
  • is 1,2,4
  • cannot be determined from the given information

Key Concepts


Number Theory

Inequality

Algebra

Check the Answer


But try the problem first…

Answer: is 1,2,4.

Source
Suggested Reading

HANOI, 2018

Elementary Number Theory by David Burton

Try with Hints


First hint

Suppose n is a positive integer such that \(2^{n}+11 \) is divisible by \(2^{k}-1\). Let n=qk+r where q,r are nonnegetive integers and \( 0 \leq r \lt k\). We have \(2^{n}+11=2^{kq+r}+11=2^{r}(2^{kq}-1)+(2^{r}+11)\) in comparision with \( 2^{k}-1\) implies \(2^{r}+11 \) in comparision with \(2^{k}-1\).

Second Hint

Thus we have \(2^{r}+11 \geq 2^{k}-1\) and \(r \lt k\) Then \(k \leq 4\).

Final Step

By calculating for k=1,2,3,4 we obtain k=1,2,4..

Subscribe to Cheenta at Youtube