Difference between revisions of "2008 Indonesia MO Problems/Problem 5"

Latest revision as of 19:47, 3 February 2024

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

@@ Line 28: / Line 28: @@
 \end{align*}</cmath>
 and so <math>\frac{2^m + b}{b \cdot 2^m + 1}</math> can not be an integer.  Therefore, <math>2^m - \frac{2^m + b}{b \cdot 2^m + 1} = b \cdot \frac{4^m - 1}{b \cdot 2^m + 1}</math> is not an integer.  Since <math>b</math> is an integer and the product of integers result in another integer, we must have <math>\frac{4^m - 1}{b \cdot 2^m + 1}</math> not be an integer.  This contradicts <math>\frac{4^m - 1}{b \cdot 2^m + 1}</math> being an integer, so by proof by contradiction, <math>b = 1</math> and so <math>n = 2^m + 1</math>.
+===Solution 3 (credit to dskull16)===
+First, let <math>2^m = x</math> for notational convenience. Then we get that <math>n|x^2-1</math> and <math>x|n-1</math>, the second of which means that
+<math>n-1 = ax</math> for some a.
+<br>
+Thus, it suffices to show that <math>x^2-1</math> is not reducible by <math>ax+1</math>  for values of <math>a>1</math>. By the factor theorem, <math>ax+1|x^2-1</math> if and only if <math>-\frac{1}{a}</math> is a root of <math>x^2-1</math>. This is only true when <math>a=1</math> so it must be the case that <math>n=2^m+1</math>.
 ==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

Page

Toolbox

Search