Difference between revisions of "2011 USAJMO Problems/Problem 1"
(→Solution) |
|||
Line 3: | Line 3: | ||
==Solution== | ==Solution== | ||
− | Let <math>2^n + 12^n + 2011^n = x^2</math> | + | Let <math>2^n + 12^n + 2011^n = x^2</math>. |
− | <math>(-1)^n + 1 \equiv x^2 \pmod {3}</math>. | + | Then <math>(-1)^n + 1 \equiv x^2 \pmod {3}</math>. |
Since all perfect squares are congruent to 0 or 1 modulo 3, this means that n must be odd. | Since all perfect squares are congruent to 0 or 1 modulo 3, this means that n must be odd. | ||
Proof by Contradiction: | Proof by Contradiction: | ||
Line 11: | Line 11: | ||
Then consider the equation | Then consider the equation | ||
<math>2^n + 12^n = x^2 - 2011^n</math>. | <math>2^n + 12^n = x^2 - 2011^n</math>. | ||
− | From modulo 2, we easily | + | From modulo 2, we easily know x is odd. Let <math>x = 2a + 1</math>, where a is an integer. |
<math>2^n + 12^n = 4a^2 + 4a + 1 - 2011^n</math>. | <math>2^n + 12^n = 4a^2 + 4a + 1 - 2011^n</math>. | ||
Dividing by 4, | Dividing by 4, | ||
Line 17: | Line 17: | ||
Since <math>n \ge 2</math>, <math>n-2 \ge 0</math>, so <math>2^{n-2}</math> similarly, the entire LHS is an integer, and so are <math>a^2</math> and <math>a</math>. Thus, <math> \dfrac {1}{4} (1 - 2011^n})</math> must be an integer. | Since <math>n \ge 2</math>, <math>n-2 \ge 0</math>, so <math>2^{n-2}</math> similarly, the entire LHS is an integer, and so are <math>a^2</math> and <math>a</math>. Thus, <math> \dfrac {1}{4} (1 - 2011^n})</math> must be an integer. | ||
Let <math> \dfrac {1}{4} (1 - 2011^n}) = k</math>. Then we have <math>1- 2011^n = 4k</math>. | Let <math> \dfrac {1}{4} (1 - 2011^n}) = k</math>. Then we have <math>1- 2011^n = 4k</math>. | ||
− | <math>1- 2011^n \equiv 0 \pmod {4}</math> | + | <math>1- 2011^n \equiv 0 \pmod {4}</math>. |
<math>(-1)^n \equiv 1 \pmod {4}</math>. | <math>(-1)^n \equiv 1 \pmod {4}</math>. | ||
Thus, n is even. | Thus, n is even. | ||
However, I have already shown that <math>n</math> must be odd. This is a contradiction. Therefore, <math>n</math> is not greater than or equal to 2, and must hence be less than 2. The only positive integer less than 2 is 1. | However, I have already shown that <math>n</math> must be odd. This is a contradiction. Therefore, <math>n</math> is not greater than or equal to 2, and must hence be less than 2. The only positive integer less than 2 is 1. | ||
-hrithikguy | -hrithikguy | ||
− | |||
==Solution 2== | ==Solution 2== |
Revision as of 16:13, 5 July 2014
Find, with proof, all positive integers for which is a perfect square.
Contents
[hide]Solution
Let . Then . Since all perfect squares are congruent to 0 or 1 modulo 3, this means that n must be odd. Proof by Contradiction: I will show that the only value of that satisfies is . Assume that . Then consider the equation . From modulo 2, we easily know x is odd. Let , where a is an integer. . Dividing by 4, $2^{n-2} + 3^n \cdot 4^{n-1} = a^2 + a + \dfrac {1}{4} (1 - 2011^n})$ (Error compiling LaTeX. Unknown error_msg). Since , , so similarly, the entire LHS is an integer, and so are and . Thus, $\dfrac {1}{4} (1 - 2011^n})$ (Error compiling LaTeX. Unknown error_msg) must be an integer. Let $\dfrac {1}{4} (1 - 2011^n}) = k$ (Error compiling LaTeX. Unknown error_msg). Then we have . . . Thus, n is even. However, I have already shown that must be odd. This is a contradiction. Therefore, is not greater than or equal to 2, and must hence be less than 2. The only positive integer less than 2 is 1. -hrithikguy
Solution 2
If , then , a perfect square.
If is odd, then .
Since all perfect squares are congruent to , we have that is not a perfect square for odd .
If is even, then .
Since , we have that is not a perfect square for even .
Thus, is the only positive integer for which is a perfect square.
Solution 3
Looking at residues mod 3, we see that must be odd, since even values of leads to . Also as shown in solution 2, for , must be even. Hence, for , can neither be odd nor even. The only possible solution is then , which indeed works.
Solution 4
Take the whole expression mod 12. Note that the perfect squares can only be of the form 0, 1, 4 or 9 (mod 12). Use a chart if you believe this isn't true. Note that since the problem is asking for positive integers, is always divisible by 12, so this will be disregarded in this process. If is even, then and . Therefore, the sum in the problem is congruent to , which cannot be a perfect square. Now we check the case for which is an odd number greater than 1. Then and . Therefore, this sum would be congruent to , which cannot be a perfect square. The only case we have not checked is . If , then the sum in the problem is equal to . Therefore the only possible value of such that is a perfect square is . The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.