2008 Indonesia MO Problems/Problem 5

Problem

Let $m,n > 1$ are integers which satisfy $n|4^m - 1$ and $2^m|n - 1$. Is it a must that $n = 2^{m} + 1$?

Solutions

Solution 1 (credit to mehmetcantu)

Since $n|4^m - 1$ and $2^m|n - 1$, we must have $n \cdot 2^m | (4^m - 1) \cdot (n -1)$. Expanding $(4^m - 1) \cdot (n -1)$ results in $n \cdot 4^m - 4^m - n + 1$. Note that both $n \cdot 4^m$ and $n \cdot 4^m - 4^m - n + 1$ are multiples of $n \cdot 2^m$, and so $4^m + n - 1$ is also a multiple of $n \cdot 2^m$. Therefore, \begin{align*} 4^m + n - 1 &\ge n \cdot 2^m \\ 4^m - 1 &\ge n \cdot 2^m - n \\ (2^m + 1)(2^m - 1) &\ge n(2^m - 1) \\ 2^m + 1 &\ge n \\ 2^m &\ge n-1, \end{align*} but we must also have $2^m \le n-1$ because $2^m|n - 1$. As a result, $2^m = n - 1$ and so $n = 2^m + 1$.

Solution 2

Since $2^m|n - 1$, we must have $b \cdot 2^m = n-1$ for a positive integer $b$. Then by solving for $n$ and doing some substitution, we must have $\frac{4^m - 1}{b \cdot 2^m + 1}$ be an integer. Now we need to show that if $\frac{4^m - 1}{b \cdot 2^m + 1}$ is an integer, then $b = 1$.


Assume that there is $b > 1$ such that $\frac{4^m - 1}{b \cdot 2^m + 1}$ is an integer. Consider the fraction $b \cdot \frac{4^m - 1}{b \cdot 2^m + 1} = \frac{b \cdot 4^m - b}{b \cdot 2^m + 1} = 2^m - \frac{2^m + b}{b \cdot 2^m + 1}$. Since $b > 1$ and $2^m - 1 > 0$, we must have \begin{align*} b \cdot 2^m - b &> 2^m - 1 \\ b \cdot 2^m + 1 &> b + 2^m, \end{align*} and so $\frac{2^m + b}{b \cdot 2^m + 1}$ can not be an integer. Therefore, $2^m - \frac{2^m + b}{b \cdot 2^m + 1} = b \cdot \frac{4^m - 1}{b \cdot 2^m + 1}$ is not an integer. Since $b$ is an integer and the product of integers result in another integer, we must have $\frac{4^m - 1}{b \cdot 2^m + 1}$ not be an integer. This contradicts $\frac{4^m - 1}{b \cdot 2^m + 1}$ being an integer, so by proof by contradiction, $b = 1$ and so $n = 2^m + 1$.

Solution 3 (credit to dskull16)

First, let $2^m = x$ for notational convenience. Then we get that $n|x^2-1$ and $x|n-1$, the second of which means that $n-1 = ax$ for some a.


Thus, it suffices to show that $x^2-1$ is not reducible by $ax+1$ for values of $a>1$. By the factor theorem, $ax+1|x^2-1$ if and only if $-\frac{1}{a}$ is a root of $x^2-1$. This is only true when $a=1$ so it must be the case that $n=2^m+1$.

See Also

2008 Indonesia MO (Problems)
Preceded by
Problem 4
1 2 3 4 5 6 7 8 Followed by
Problem 6
All Indonesia MO Problems and Solutions