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.

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..

## Other useful links

- https://www.cheenta.com/problem-based-on-inequalities-hanoi-2018/
- https://www.youtube.com/watch?v=ST58GTF95t4&t=140s

Google