Select Page

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

But try the problem first…

Source

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