Difference between revisions of "2008 Indonesia MO Problems/Problem 5"
Rockmanex3 (talk | contribs) (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 18:47, 3 February 2024
Contents
[hide]Problem
Let are integers which satisfy and . Is it a must that ?
Solutions
Solution 1 (credit to mehmetcantu)
Since and , we must have . Expanding results in . Note that both and are multiples of , and so is also a multiple of . Therefore, but we must also have because . As a result, and so .
Solution 2
Since , we must have for a positive integer . Then by solving for and doing some substitution, we must have be an integer. Now we need to show that if is an integer, then .
Assume that there is such that is an integer. Consider the fraction . Since and , we must have
and so can not be an integer. Therefore, is not an integer. Since is an integer and the product of integers result in another integer, we must have not be an integer. This contradicts being an integer, so by proof by contradiction, and so .
Solution 3 (credit to dskull16)
First, let for notational convenience. Then we get that and , the second of which means that for some a.
Thus, it suffices to show that is not reducible by for values of . By the factor theorem, if and only if is a root of . This is only true when so it must be the case that .
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 |