Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

2008 Indonesia MO Problems/Problem 5

Revision as of 02:38, 23 June 2021 by Rockmanex3 (talk | contribs) (Solutions to Problem 5 (solution 1 credit to mehmetcantu) -- two proof approaches!)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2008_Indonesia_MO_Problems/Problem_5&oldid=156650"