Difference between revisions of "2011 USAJMO Problems/Problem 1"
Morgandaciuk (talk | contribs) (→Solution 1) |
Morgandaciuk (talk | contribs) (→Solution 1) |
||
Line 3: | Line 3: | ||
==Solution 1== | ==Solution 1== | ||
− | Let <math>2^n + 12^n + 2011^n = x^2</math>. | + | Let <math>2^n + 12^n + 2011^n = x^2</math>. |
− | Then <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: | ||
− | + | We wish to show that the only value of <math>n</math> that satisfies is <math>n = 1</math>. | |
Assume that <math>n \ge 2</math>. | Assume that <math>n \ge 2</math>. | ||
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 know x is odd. Let <math>x = 2a + 1</math>, where a is an integer. | + | 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, | ||
− | <math>2^{n-2} + 3^n \cdot 4^{n-1} = a^2 + a + \dfrac {1}{4} (1 - 2011^n)</math>. | + | <math>2^{n-2} + 3^n \cdot 4^{n-1} = a^2 + a + \dfrac {1}{4} (1 - 2011^n)</math>. |
− | 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>. |
− | Let <math> \dfrac {1}{4} (1 - 2011^n) = k</math>. Then we have <math>1- 2011^n = 4k</math>. | + | Thus, <math> \dfrac {1}{4} (1 - 2011^n)</math> must be an integer. |
− | <math>1- 2011^n \equiv 0 \pmod {4}</math>. | + | Let <math> \dfrac {1}{4} (1 - 2011^n) = k</math>. |
− | <math>(-1)^n \equiv 1 \pmod {4}</math>. | + | Then we have <math>1- 2011^n = 4k</math>. |
− | Thus, n is even. | + | <math>1- 2011^n \equiv 0 \pmod {4}</math>. |
− | However, | + | <math>(-1)^n \equiv 1 \pmod {4}</math>. |
− | + | Thus, n is even. | |
+ | However, it has already been 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. | ||
==Solution 2== | ==Solution 2== |
Revision as of 19:23, 23 March 2015
Find, with proof, all positive integers for which is a perfect square.
Contents
[hide]Solution 1
Let . Then . Since all perfect squares are congruent to 0 or 1 modulo 3, this means that n must be odd. Proof by Contradiction: We wish to 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, . Since , , so similarly, the entire LHS is an integer, and so are and . Thus, must be an integer. Let . Then we have . . . Thus, n is even. However, it has already been 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.
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.