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

(Solutions to Problem 5 (solution 1 credit to mehmetcantu) -- two proof approaches!)
 
(Solutions)
 
Line 28: Line 28:
 
\end{align*}</cmath>
 
\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>.
 
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==
 
==See Also==

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

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