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

Difference between revisions of "2011 USAJMO Problems/Problem 1"

(→‎Solution 3)
 
(16 intermediate revisions by 11 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:
−
I will show that the only value of <math>n</math> that satisfies is <math>n = 1</math>.
+
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 that 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, 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.
+
<math>(-1)^n \equiv 1 \pmod {4}</math>.  
−
-hrithikguy
+
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 39: Line 44:
  
 
==Solution 3==
 
==Solution 3==
−
Looking at residues <math>mod</math> <math>3</math>, 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 20:49, 1 October 2021

Problem

Find, with proof, all positive integers $n$ for which $2^n + 12^n + 2011^n$ is a perfect square.

Solution

The answer is $n=1$, which is easily verified to be a valid integer $n$. Notice that \[2^n+12^n+2011^n\equiv 2^n+7^n \pmod{12}.\] Then for $n\geq 2$, we have $2^n+7^n\equiv 3,5 \pmod{12}$ depending on the parity of $n$. But perfect squares can only be $0,1,4,9\pmod{12}$, contradiction. Therefore, we are done. $\blacksquare$

Solution 1

Let $2^n + 12^n + 2011^n = x^2$. Then $(-1)^n + 1 \equiv x^2 \pmod {3}$. 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 $n$ that satisfies is $n = 1$. Assume that $n \ge 2$. Then consider the equation $2^n + 12^n = x^2 - 2011^n$. From modulo 2, we easily know x is odd. Let $x = 2a + 1$, where a is an integer. $2^n + 12^n = 4a^2 + 4a + 1 - 2011^n$. Dividing by 4, $2^{n-2} + 3^n \cdot 4^{n-1} = a^2 + a + \dfrac {1}{4} (1 - 2011^n)$. Since $n \ge 2$, $n-2 \ge 0$, so $2^{n-2}$ similarly, the entire LHS is an integer, and so are $a^2$ and $a$. Thus, $\dfrac {1}{4} (1 - 2011^n)$ must be an integer. Let $\dfrac {1}{4} (1 - 2011^n) = k$. Then we have $1- 2011^n = 4k$. $1- 2011^n \equiv 0 \pmod {4}$. $(-1)^n \equiv 1 \pmod {4}$. Thus, n is even. However, it has already been shown that $n$ must be odd. This is a contradiction. Therefore, $n$ 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 $n = 1$, then $2^n + 12^n + 2011^n = 2025 = 45^2$, a perfect square.

If $n > 1$ is odd, then $2^n + 12^n + 2011^n \equiv 0 + 0 + (-1)^n \equiv 3 \pmod{4}$.

Since all perfect squares are congruent to $0,1 \pmod{4}$, we have that $2^n+12^n+2011^n$ is not a perfect square for odd $n > 1$.

If $n = 2k$ is even, then $(2011^k)^2 < 2^{2k}+12^{2k}+2011^{2k}$ $= 4^k + 144^k + 2011^{2k} <$ $2011^k + 2011^k + 2011^{2k} < (2011^k+1)^2$.

Since $(2011^k)^2 < 2^n+12^n+2011^n < (2011^k+1)^2$, we have that $2^n+12^n+2011^n$ is not a perfect square for even $n$.

Thus, $n = 1$ is the only positive integer for which $2^n + 12^n + 2011^n$ is a perfect square.


Solution 3

Looking at residues mod 3, we see that $n$ must be odd, since even values of $n$ leads to $2^n + 12^n + 2011^n = 2 \pmod{3}$. Also as shown in solution 2, for $n>1$, $n$ must be even. Hence, for $n>1$, $n$ can neither be odd nor even. The only possible solution is then $n=1$, 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, $12^n$ is always divisible by 12, so this will be disregarded in this process. If $n$ is even, then $2^n \equiv 4 \pmod{12}$ and $2011^n \equiv 7^n \equiv 1 \pmod {12}$. Therefore, the sum in the problem is congruent to $5 \pmod {12}$, which cannot be a perfect square. Now we check the case for which $n$ is an odd number greater than 1. Then $2^n \equiv 8 \pmod{12}$ and $2011^n \equiv 7^n \equiv 7 \pmod {12}$. Therefore, this sum would be congruent to $3 \pmod {12}$, which cannot be a perfect square. The only case we have not checked is $n=1$. If $n=1$, then the sum in the problem is equal to $2+12+2011=2025=45^2$. Therefore the only possible value of $n$ such that $2^n+12^n+2011^n$ is a perfect square is $n=1$.

Solution 5

We will first take the expression modulo $3$. We get $2^n+12^n+2011^n \equiv -1^n+1^n \pmod 3$.

Lemma 1: All perfect squares are equal to $0$ or $1$ modulo $3$. We can prove this by testing the residues modulo $3$. We have $0^2 \equiv 0 \pmod 3$, $1^2 \equiv 1 \pmod 3$, and $2^2 \equiv 1 \pmod 3$, so the lemma is true.

We know that if $n$ is odd, $-1^n+1^n \equiv 0 \pmod 3$, which satisfies the lemma's conditions. However, if $n$ is even, we get $2 \pmod 3$, which does not satisfy the lemma's conditions. So, we can conclude that $n$ is odd.

Now, we take the original expression modulo $4$. For right now, we will assume that $n>1$, and test $n=1$ later. For $n>1$, $2^n \equiv 0 \pmod 4$, so $2^n+12^n+2011^n=-1^n \pmod 4$.

Lemma 2: All perfect squares are equal to $0$ or $1$ modulo $4$. We can prove this by testing the residues modulo $4$. We have $0^2 \equiv 0 \pmod 4$, $1^2 \equiv 1 \pmod 4$, $2^2 \equiv 0 \pmod 4$, and $3^2 \equiv 1 \pmod 4$, so the lemma is true.

We know that if $n$ is even, $-1^n \equiv 0 \pmod 4$, which satisfies the lemma's conditions. However, if $n$ is odd, $-1^n \equiv -1 \equiv 3 \pmod 4$, which does not satisfy the lemma's conditions. Therefore, $n$ 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 $n=1$. We know that $2^1+12^1+2011^1=45^2$, so the only integer is $\boxed{n=1}$.

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2011_USAJMO_Problems/Problem_1&oldid=163010"