Difference between revisions of "2011 USAJMO Problems/Problem 1"
(→Solution 3) |
|||
(15 intermediate revisions by 10 users not shown) | |||
Line 1: | Line 1: | ||
+ | ==Problem== | ||
Find, with proof, all positive integers <math>n</math> for which <math>2^n + 12^n + 2011^n</math> is a perfect square. | Find, with proof, all positive integers <math>n</math> for which <math>2^n + 12^n + 2011^n</math> is a perfect square. | ||
==Solution== | ==Solution== | ||
+ | The answer is <math>n=1</math>, which is easily verified to be a valid integer <math>n</math>. | ||
+ | Notice that <cmath>2^n+12^n+2011^n\equiv 2^n+7^n \pmod{12}.</cmath> Then for <math>n\geq 2</math>, we have <math>2^n+7^n\equiv 3,5 \pmod{12}</math> depending on the parity of <math>n</math>. But perfect squares can only be <math>0,1,4,9\pmod{12}</math>, contradiction. Therefore, we are done. <math>\blacksquare</math> | ||
− | Let <math>2^n + 12^n + 2011^n = x^2</math> | + | ==Solution 1== |
− | <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. | + | Let <math>2^n + 12^n + 2011^n = x^2</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. | ||
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 | + | 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>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 | + | 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 | + | 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== | ||
Line 40: | Line 45: | ||
==Solution 3== | ==Solution 3== | ||
Looking at residues mod 3, we see that <math>n</math> must be odd, since even values of <math>n</math> leads to <math>2^n + 12^n + 2011^n = 2 \pmod{3}</math>. Also as shown in solution 2, for <math>n>1</math>, <math>n</math> must be even. Hence, for <math>n>1</math>, <math>n</math> can neither be odd nor even. The only possible solution is then <math>n=1</math>, which indeed works. | Looking at residues mod 3, we see that <math>n</math> must be odd, since even values of <math>n</math> leads to <math>2^n + 12^n + 2011^n = 2 \pmod{3}</math>. Also as shown in solution 2, for <math>n>1</math>, <math>n</math> must be even. Hence, for <math>n>1</math>, <math>n</math> can neither be odd nor even. The only possible solution is then <math>n=1</math>, 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). Note that since the problem is asking for positive integers, <math>12^n</math> is always divisible by 12, so this will be disregarded in this process. If <math>n</math> is even, then <math>2^n \equiv 4 \pmod{12}</math> and <math>2011^n \equiv 7^n \equiv 1 \pmod {12}</math>. Therefore, the sum in the problem is congruent to <math>5 \pmod {12}</math>, which cannot be a perfect square. Now we check the case for which <math>n</math> is an odd number greater than 1. Then <math>2^n \equiv 8 \pmod{12}</math> and <math>2011^n \equiv 7^n \equiv 7 \pmod {12}</math>. Therefore, this sum would be congruent to <math>3 \pmod {12}</math>, which cannot be a perfect square. The only case we have not checked is <math>n=1</math>. If <math>n=1</math>, then the sum in the problem is equal to <math>2+12+2011=2025=45^2</math>. Therefore the only possible value of <math>n</math> such that <math>2^n+12^n+2011^n</math> is a perfect square is <math>n=1</math>. | ||
+ | |||
+ | ==Solution 5== | ||
+ | We will first take the expression modulo <math>3</math>. We get <math>2^n+12^n+2011^n \equiv -1^n+1^n \pmod 3</math>. | ||
+ | |||
+ | Lemma 1: All perfect squares are equal to <math>0</math> or <math>1</math> modulo <math>3</math>. | ||
+ | We can prove this by testing the residues modulo <math>3</math>. We have <math>0^2 \equiv 0 \pmod 3</math>, <math>1^2 \equiv 1 \pmod 3</math>, and <math>2^2 \equiv 1 \pmod 3</math>, so the lemma is true. | ||
+ | |||
+ | We know that if <math>n</math> is odd, <math>-1^n+1^n \equiv 0 \pmod 3</math>, which satisfies the lemma's conditions. However, if <math>n</math> is even, we get <math>2 \pmod 3</math>, which does not satisfy the lemma's conditions. So, we can conclude that <math>n</math> is odd. | ||
+ | |||
+ | Now, we take the original expression modulo <math>4</math>. For right now, we will assume that <math>n>1</math>, and test <math>n=1</math> later. For <math>n>1</math>, <math>2^n \equiv 0 \pmod 4</math>, so <math>2^n+12^n+2011^n=-1^n \pmod 4</math>. | ||
+ | |||
+ | Lemma 2: All perfect squares are equal to <math>0</math> or <math>1</math> modulo <math>4</math>. | ||
+ | We can prove this by testing the residues modulo <math>4</math>. We have <math>0^2 \equiv 0 \pmod 4</math>, <math>1^2 \equiv 1 \pmod 4</math>, <math>2^2 \equiv 0 \pmod 4</math>, and <math>3^2 \equiv 1 \pmod 4</math>, so the lemma is true. | ||
+ | |||
+ | We know that if <math>n</math> is even, <math>-1^n \equiv 0 \pmod 4</math>, which satisfies the lemma's conditions. However, if <math>n</math> is odd, <math>-1^n \equiv -1 \equiv 3 \pmod 4</math>, which does not satisfy the lemma's conditions. Therefore, <math>n</math> must be even. | ||
+ | |||
+ | However, a number cannot be even and odd at the same time, so this is impossible. Now, we only have to test <math>n=1</math>. We know that <math>2^1+12^1+2011^1=45^2</math>, so the only integer is <math>\boxed{n=1}</math>. | ||
+ | |||
+ | {{MAA Notice}} |
Latest revision as of 21:49, 1 October 2021
Problem
Find, with proof, all positive integers for which
is a perfect square.
Solution
The answer is , which is easily verified to be a valid integer
.
Notice that
Then for
, we have
depending on the parity of
. But perfect squares can only be
, contradiction. Therefore, we are done.
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). 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
.
Solution 5
We will first take the expression modulo . We get
.
Lemma 1: All perfect squares are equal to or
modulo
.
We can prove this by testing the residues modulo
. We have
,
, and
, so the lemma is true.
We know that if is odd,
, which satisfies the lemma's conditions. However, if
is even, we get
, which does not satisfy the lemma's conditions. So, we can conclude that
is odd.
Now, we take the original expression modulo . For right now, we will assume that
, and test
later. For
,
, so
.
Lemma 2: All perfect squares are equal to or
modulo
.
We can prove this by testing the residues modulo
. We have
,
,
, and
, so the lemma is true.
We know that if is even,
, which satisfies the lemma's conditions. However, if
is odd,
, which does not satisfy the lemma's conditions. Therefore,
must be even.
However, a number cannot be even and odd at the same time, so this is impossible. Now, we only have to test . We know that
, so the only integer is
.
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.