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 "2013 USAJMO Problems/Problem 1"
(→‎Solution 7)
 
(24 intermediate revisions by 14 users not shown)
Line 5: Line 5:
 
==Solution==
 
==Solution==
  
−
Consider the equation <math>\bmod 9</math>.
+
No, such integers do not exist.  This shall be proven by contradiction, by showing that if <math>a^5b+3</math> is a perfect cube then <math>ab^5+3</math> cannot be.
 +
 
 +
Remark that perfect cubes are always congruent to <math>0</math>, <math>1</math>, or <math>-1</math> modulo <math>9</math>.  Therefore, if <math>a^5b+3\equiv 0,1,\text{ or} -1\pmod{9}</math>, then <math>a^5b\equiv 5,6,\text{ or }7\pmod{9}</math>.
 +
 
 +
If <math>a^5b\equiv 6\pmod 9</math>, then note that <math>3|b</math>.  (This is because if <math>3|a</math> then <math>a^5b\equiv 0\pmod 9</math>.)  Therefore <math>ab^5\equiv 0\pmod 9</math> and <math>ab^5+3\equiv 3\pmod 9</math>, contradiction.
 +
 
 +
Otherwise, either <math>a^5b\equiv 5\pmod 9</math> or <math>a^5b\equiv 7\pmod 9</math>.  Note that since <math>a^6b^6</math> is a perfect sixth power, and since neither <math>a</math> nor <math>b</math> contains a factor of <math>3</math>, <math>a^6b^6\equiv 1\pmod 9</math>.  If <math>a^5b\equiv 5\pmod 9</math>, then <cmath>a^6b^6\equiv (a^5b)(ab^5)\equiv 5ab^5\equiv 1\pmod 9\implies ab^5\equiv 2\pmod 9.</cmath>  Similarly, if <math>a^5b\equiv 7\pmod 9</math>, then <cmath>a^6b^6\equiv (a^5b)(ab^5)\equiv 7ab^5\equiv 1\pmod 9\implies ab^5\equiv 4\pmod 9.</cmath>  Therefore <math>ab^5+3\equiv 5,7\pmod 9</math>, contradiction.
 +
 
 +
Therefore no such integers exist.
 +
 
 +
Amkan2022
 +
 
 +
==Solution 2==
 +
We shall prove that such integers do not exist via contradiction.
 +
Suppose that <math>a^5b + 3 = x^3</math> and <math>ab^5 + 3 = y^3</math> for integers x and y. Rearranging terms gives <math>a^5b = x^3 - 3</math> and <math>ab^5 = y^3 - 3</math>. Solving for a and b (by first multiplying the equations together and taking the sixth root) gives a = <math>(x^3 - 3)^\frac{5}{24} (y^3 - 3)^\frac{-1}{24}</math> and b = <math>(y^3 - 3)^\frac{5}{24} (x^3 - 3)^\frac{-1}{24}</math>. Consider a prime p in the prime factorization of <math>x^3 - 3</math> and <math>y^3 - 3</math>. If it has power <math>r_1</math> in <math>x^3 - 3</math> and power <math>r_2</math> in <math>y^3 - 3</math>, then <math>5r_1</math> - <math>r_2</math> is a multiple of 24 and <math>5r_2</math> - <math>r_1</math> also is a multiple of 24.
 +
 
 +
Adding and subtracting the divisions gives that <math>r_1</math> - <math>r_2</math> divides 12. (actually, <math>r_1 - r_2</math> is a multiple of 4, as you can verify if <math>\{^{5r_1 - r_2 = 24}_{5r_2 - r_1 = 48}</math>. So the rest of the proof is invalid.) Because <math>5r_1</math> - <math>r_2</math> also divides 12, <math>4r_1</math> divides 12 and thus <math>r_1</math> divides 3. Repeating this trick for all primes in <math>x^3 - 3</math>, we see that <math>x^3 - 3</math> is a perfect cube, say <math>q^3</math>. Then <math>x^3 - q^3 = 3,</math> and <math>(x-q)(x^2 + xq + q^2) = 3</math>, so that <math>x - q = 1</math> and <math>x^2 + xq + q^2 = 3</math>. Clearly, this system of equations has no integer solutions for <math>x</math> or <math>q</math>, a contradiction, hence completing the proof.
 +
 
 +
Therefore no such integers exist.
 +
 
 +
==Solution 3==
 +
Let <math>a^5b+3=x^3</math> and <math>ab^5+3=y^3</math>. Then, <math>a^5b=x^3-3</math>, <math>ab^5=y^3-3</math>, and <cmath>(ab)^6=(x^3-3)(y^3-3)</cmath>
 +
Now take <math>\text{mod }9</math> (recall that perfect cubes <math>\equiv -1,0,1\pmod{9}</math> and perfect sixth powers <math>\equiv 0,1\pmod{9}</math>) on both sides. There are <math>3\times 3=9</math> cases to consider on what values <math>\text{mod }9</math> that <math>x^3</math> and <math>y^3</math> take. Checking these <math>9</math> cases, we see that only <math>x^3\equiv y^3\equiv 0\pmod{9}</math> or <math>x\equiv y\equiv 0\pmod{3}</math> yield a valid residue <math>\text{mod }9</math> (specifically, <math>(x^3-3)(y^3-3)\equiv 0\pmod{9}</math>). But this means that <math>3\mid ab</math>, so <math>729\mid (ab)^6</math> so <cmath>729\mid (x^3-3)(y^3-3)\iff 729\mid (27x'^3-3)(27y'^3-3)\iff 81\mid (9x'^3-1)(9y'^3-1)</cmath> contradiction.
 +
 
 +
==Solution 4==
 +
If <math>a^5b+3</math> is a perfect cube, then <math>a^5b</math> can be one of <math>5,6,7 \pmod 9</math>, so <math>(a^5b)^5 = a^{25} b^5</math> can be one of <math>5^5 \equiv 2</math>, <math>6^5 \equiv 0</math>, or <math>7^5 \equiv 4 \pmod 9</math>. If <math>a</math> were divisible by <math>3</math>, we'd have <math>a^5 b \equiv 0 \pmod 9</math>, which we've ruled out. So <math>\gcd(a,9) = 1</math>, which means <math>a^6 \equiv 1 \pmod 9</math>, and therefore <math>a^{25} b^5 \equiv ab^5 \pmod 9</math>.
 +
 
 +
We've shown that <math>a b^5</math> can be one of <math>0, 2, 4 \pmod 9</math>, so <math>ab^5 + 3</math> can be one of <math>3, 5, 7 \pmod 9</math>. None of these are possibilities for a perfect cube, so if <math>a^5b+3</math> is a perfect cube, <math>ab^5+3</math> cannot be.
 +
 
 +
==Solution 5==
 +
 
 +
As in previous solutions, notice <math>ab^5,a^5b \equiv 5,6,7 \pmod 9</math>. Now multiplying gives <math>a^6b^6</math>, which is only <math>0,1 \pmod 9</math>, so after testing all cases we find that <math>ab^5\equiv a^5b \equiv 6 \mod 9</math>. Then since <math>\phi (9) = 6</math>, <math>ab^5\equiv \frac{a}{b}\pmod 9</math> and <math>a^5b \equiv \frac{b}{a}\pmod 9</math> (Note that <math>a,b</math> cannot be <math>0\pmod 9</math>). Thus we find that the inverse of <math>6</math> is itself under modulo <math>9</math>, a contradiction.
 +
 
 +
==Solution 6==
 +
I claim there are no such a or b such that both expressions are cubes.
 +
 
 +
Assume to the contrary <math>a^5b +3</math> and <math>ab^5 + 3</math> are cubes.
 +
 
 +
'''Lemma 1''': If <math>a^5b +3</math> and <math>ab^5 + 3</math> are cubes, then <math>ab^5, a^5b \equiv 5,7 \pmod 9</math>
 +
 
 +
'''Proof''' Since cubes are congruent to any of <math>0, 1, -1 \pmod 9</math>, <math>ab^5,a^5b \equiv 5,6,7 \pmod 9</math>. But if <math>ab^5 \equiv 6 \pmod 9</math>, <math>3|a</math>, so <math>a^5b \equiv 0 \pmod 9</math>, contradiction. A similar argument can be made for <math>ab^5 \neq 6 \pmod 9</math>.
 +
 
 +
 
 +
'''Lemma 2''': If k is a perfect 6th power, then <math>k \equiv 0,1 \pmod 9</math>
 +
 
 +
'''Proof''': Since cubes are congruent to <math>0, 1,  -1 \pmod 9</math>, we can square, and get 6th powers are congruent to <math>0, 1 \pmod 9</math>.
 +
 
 +
 
 +
Since <math>ab^5 \cdot a^5b = a^6 b^6 = (ab)^6</math>, which is a perfect 6th power, by lemma 2, <math>ab^5 \cdot a^5b \equiv 0,1 \pmod 9</math>.
 +
 
 +
But, by lemma 1, <math>ab^5 \cdot a^5b \equiv 5 \cdot 5, 5 \cdot 7, 7 \cdot 7 \equiv 7, 8, 4 \pmod 9</math>.
 +
 
 +
So, <math>ab^5 \cdot a^5b</math>, which is an integer, can't go into any of the possible residue classes modulo 9, without breaking one of these lemmas. This is a contradiction, and the proof is complete. <math>\blacksquare</math>
 +
 
 +
-AlexLikeMath
 +
 
 +
 
 +
 
 +
==Solution 7==
 +
Note that <math>x^3 \equiv 0,1,-1 \pmod 9</math>. So <math>a^5b+3, ab^5+3\equiv 0,1,-1\pmod{9}</math><math>\Rightarrow a^5b, ab^5 \equiv 5,6,7 \pmod 9</math>.
 +
            <math>a^5b \equiv 5 \pmod 9 \;\;\;\;\;\; ab^5 \equiv 5 \pmod 9</math>
 +
            <math>a^5b \equiv 6 \pmod 9 \;\;\;\;\;\; ab^5 \equiv 6 \pmod 9</math>
 +
            <math>a^5b \equiv 7 \pmod 9 \;\;\;\;\;\; ab^5 \equiv 7 \pmod 9</math>.
 +
Multiplying <math>a^5b</math> and <math>ab^5</math> we get <math>(ab)^6</math>. By substituting values for <math>a^5b</math> and <math>ab^5</math> we can see that <math>(ab)^6 \equiv 0,1,3,6,7,8 \pmod 9</math> but because cubes are not <math>3,6,7 \pmod 9</math>, and squares are not <math>-1\pmod 9</math> so <math>\boxed{(ab)^6 \equiv 0,1 \pmod 9}</math>.
 +
*Case I: <math>(ab)^6\equiv 0 \pmod 9</math>.This is only true when <math>3|ab</math>. If <math>3|a,b</math> then <math>a^5b+3 \equiv 3 \pmod 9</math>, which is not a perfect cube. The same can be seen with if <math>3|a</math> then <math>a^5b+3 \equiv 3 \pmod 9</math> and if <math>3|a</math> then <math>b^5a+3 \equiv 3 \pmod 9</math>. So 6 mod 9 case is eliminated from the above relations of congruences
 +
*Case II: <math>(ab)^6\equiv 1 \pmod 9</math> for this we'll take a look at the above information regarding <math>a^5b</math> and <math>ab^5</math>. If <math>a^5b \equiv 5 \pmod 9</math> then,
 +
          <math>(ab)^6=a^5b \cdot ab^5 \equiv 5(ab^5) \pmod 9 \Rightarrow ab^5 \equiv 2 \pmod 9 \Rightarrow ab^5+3 \equiv
 +
            5 \pmod 9</math>
 +
which is not possible. Similarly, if <math>a^5b \equiv 7 \pmod 9</math> then,
 +
          <math>(ab)^6=a^5b \cdot ab^5 \equiv 7(ab^5) \pmod 9 \Rightarrow ab^5 \equiv 4 \pmod 9 \Rightarrow ab^5+3 \equiv
 +
            7 \pmod 9</math>
 +
which is not possible. So, no such integers.
 +
 
 +
-Lakshya Pamecha
 +
 
 +
==Note==
 +
After you get that <math>a^5 b \equiv 5, 6, \text{or} 7 \pmod{9}</math>, you can also bash by listing all possible residues for <math>a^5</math> and their corresponding values for <math>b</math>. At that point, you can easily see that all the solutions for <math>a</math> and <math>b</math> do not work in the other equation, meaning that there are no solutions that satisfy both equations.
 +
 
 +
{{MAA Notice}}

Latest revision as of 01:45, 10 May 2024

Problem

Are there integers $a$ and $b$ such that $a^5b+3$ and $ab^5+3$ are both perfect cubes of integers?

Solution

No, such integers do not exist. This shall be proven by contradiction, by showing that if $a^5b+3$ is a perfect cube then $ab^5+3$ cannot be.

Remark that perfect cubes are always congruent to $0$, $1$, or $-1$ modulo $9$. Therefore, if $a^5b+3\equiv 0,1,\text{ or} -1\pmod{9}$, then $a^5b\equiv 5,6,\text{ or }7\pmod{9}$.

If $a^5b\equiv 6\pmod 9$, then note that $3|b$. (This is because if $3|a$ then $a^5b\equiv 0\pmod 9$.) Therefore $ab^5\equiv 0\pmod 9$ and $ab^5+3\equiv 3\pmod 9$, contradiction.

Otherwise, either $a^5b\equiv 5\pmod 9$ or $a^5b\equiv 7\pmod 9$. Note that since $a^6b^6$ is a perfect sixth power, and since neither $a$ nor $b$ contains a factor of $3$, $a^6b^6\equiv 1\pmod 9$. If $a^5b\equiv 5\pmod 9$, then \[a^6b^6\equiv (a^5b)(ab^5)\equiv 5ab^5\equiv 1\pmod 9\implies ab^5\equiv 2\pmod 9.\] Similarly, if $a^5b\equiv 7\pmod 9$, then \[a^6b^6\equiv (a^5b)(ab^5)\equiv 7ab^5\equiv 1\pmod 9\implies ab^5\equiv 4\pmod 9.\] Therefore $ab^5+3\equiv 5,7\pmod 9$, contradiction.

Therefore no such integers exist.

Amkan2022

Solution 2

We shall prove that such integers do not exist via contradiction. Suppose that $a^5b + 3 = x^3$ and $ab^5 + 3 = y^3$ for integers x and y. Rearranging terms gives $a^5b = x^3 - 3$ and $ab^5 = y^3 - 3$. Solving for a and b (by first multiplying the equations together and taking the sixth root) gives a = $(x^3 - 3)^\frac{5}{24} (y^3 - 3)^\frac{-1}{24}$ and b = $(y^3 - 3)^\frac{5}{24} (x^3 - 3)^\frac{-1}{24}$. Consider a prime p in the prime factorization of $x^3 - 3$ and $y^3 - 3$. If it has power $r_1$ in $x^3 - 3$ and power $r_2$ in $y^3 - 3$, then $5r_1$ - $r_2$ is a multiple of 24 and $5r_2$ - $r_1$ also is a multiple of 24.

Adding and subtracting the divisions gives that $r_1$ - $r_2$ divides 12. (actually, $r_1 - r_2$ is a multiple of 4, as you can verify if $\{^{5r_1 - r_2 = 24}_{5r_2 - r_1 = 48}$. So the rest of the proof is invalid.) Because $5r_1$ - $r_2$ also divides 12, $4r_1$ divides 12 and thus $r_1$ divides 3. Repeating this trick for all primes in $x^3 - 3$, we see that $x^3 - 3$ is a perfect cube, say $q^3$. Then $x^3 - q^3 = 3,$ and $(x-q)(x^2 + xq + q^2) = 3$, so that $x - q = 1$ and $x^2 + xq + q^2 = 3$. Clearly, this system of equations has no integer solutions for $x$ or $q$, a contradiction, hence completing the proof.

Therefore no such integers exist.

Solution 3

Let $a^5b+3=x^3$ and $ab^5+3=y^3$. Then, $a^5b=x^3-3$, $ab^5=y^3-3$, and \[(ab)^6=(x^3-3)(y^3-3)\] Now take $\text{mod }9$ (recall that perfect cubes $\equiv -1,0,1\pmod{9}$ and perfect sixth powers $\equiv 0,1\pmod{9}$) on both sides. There are $3\times 3=9$ cases to consider on what values $\text{mod }9$ that $x^3$ and $y^3$ take. Checking these $9$ cases, we see that only $x^3\equiv y^3\equiv 0\pmod{9}$ or $x\equiv y\equiv 0\pmod{3}$ yield a valid residue $\text{mod }9$ (specifically, $(x^3-3)(y^3-3)\equiv 0\pmod{9}$). But this means that $3\mid ab$, so $729\mid (ab)^6$ so \[729\mid (x^3-3)(y^3-3)\iff 729\mid (27x'^3-3)(27y'^3-3)\iff 81\mid (9x'^3-1)(9y'^3-1)\] contradiction.

Solution 4

If $a^5b+3$ is a perfect cube, then $a^5b$ can be one of $5,6,7 \pmod 9$, so $(a^5b)^5 = a^{25} b^5$ can be one of $5^5 \equiv 2$, $6^5 \equiv 0$, or $7^5 \equiv 4 \pmod 9$. If $a$ were divisible by $3$, we'd have $a^5 b \equiv 0 \pmod 9$, which we've ruled out. So $\gcd(a,9) = 1$, which means $a^6 \equiv 1 \pmod 9$, and therefore $a^{25} b^5 \equiv ab^5 \pmod 9$.

We've shown that $a b^5$ can be one of $0, 2, 4 \pmod 9$, so $ab^5 + 3$ can be one of $3, 5, 7 \pmod 9$. None of these are possibilities for a perfect cube, so if $a^5b+3$ is a perfect cube, $ab^5+3$ cannot be.

Solution 5

As in previous solutions, notice $ab^5,a^5b \equiv 5,6,7 \pmod 9$. Now multiplying gives $a^6b^6$, which is only $0,1 \pmod 9$, so after testing all cases we find that $ab^5\equiv a^5b \equiv 6 \mod 9$. Then since $\phi (9) = 6$, $ab^5\equiv \frac{a}{b}\pmod 9$ and $a^5b \equiv \frac{b}{a}\pmod 9$ (Note that $a,b$ cannot be $0\pmod 9$). Thus we find that the inverse of $6$ is itself under modulo $9$, a contradiction.

Solution 6

I claim there are no such a or b such that both expressions are cubes.

Assume to the contrary $a^5b +3$ and $ab^5 + 3$ are cubes.

Lemma 1: If $a^5b +3$ and $ab^5 + 3$ are cubes, then $ab^5, a^5b \equiv 5,7 \pmod 9$

Proof Since cubes are congruent to any of $0, 1, -1 \pmod 9$, $ab^5,a^5b \equiv 5,6,7 \pmod 9$. But if $ab^5 \equiv 6 \pmod 9$, $3|a$, so $a^5b \equiv 0 \pmod 9$, contradiction. A similar argument can be made for $ab^5 \neq 6 \pmod 9$.


Lemma 2: If k is a perfect 6th power, then $k \equiv 0,1 \pmod 9$

Proof: Since cubes are congruent to $0, 1, -1 \pmod 9$, we can square, and get 6th powers are congruent to $0, 1 \pmod 9$.


Since $ab^5 \cdot a^5b = a^6 b^6 = (ab)^6$, which is a perfect 6th power, by lemma 2, $ab^5 \cdot a^5b \equiv 0,1 \pmod 9$.

But, by lemma 1, $ab^5 \cdot a^5b \equiv 5 \cdot 5, 5 \cdot 7, 7 \cdot 7 \equiv 7, 8, 4 \pmod 9$.

So, $ab^5 \cdot a^5b$, which is an integer, can't go into any of the possible residue classes modulo 9, without breaking one of these lemmas. This is a contradiction, and the proof is complete. $\blacksquare$

-AlexLikeMath


Solution 7

Note that $x^3 \equiv 0,1,-1 \pmod 9$. So $a^5b+3, ab^5+3\equiv 0,1,-1\pmod{9}$$\Rightarrow a^5b, ab^5 \equiv 5,6,7 \pmod 9$. 

           $a^5b \equiv 5 \pmod 9 \;\;\;\;\;\; ab^5 \equiv 5 \pmod 9$
           $a^5b \equiv 6 \pmod 9 \;\;\;\;\;\; ab^5 \equiv 6 \pmod 9$
           $a^5b \equiv 7 \pmod 9 \;\;\;\;\;\; ab^5 \equiv 7 \pmod 9$.

Multiplying $a^5b$ and $ab^5$ we get $(ab)^6$. By substituting values for $a^5b$ and $ab^5$ we can see that $(ab)^6 \equiv 0,1,3,6,7,8 \pmod 9$ but because cubes are not $3,6,7 \pmod 9$, and squares are not $-1\pmod 9$ so $\boxed{(ab)^6 \equiv 0,1 \pmod 9}$.

  • Case I: $(ab)^6\equiv 0 \pmod 9$.This is only true when $3|ab$. If $3|a,b$ then $a^5b+3 \equiv 3 \pmod 9$, which is not a perfect cube. The same can be seen with if $3|a$ then $a^5b+3 \equiv 3 \pmod 9$ and if $3|a$ then $b^5a+3 \equiv 3 \pmod 9$. So 6 mod 9 case is eliminated from the above relations of congruences
  • Case II: $(ab)^6\equiv 1 \pmod 9$ for this we'll take a look at the above information regarding $a^5b$ and $ab^5$. If $a^5b \equiv 5 \pmod 9$ then,
          $(ab)^6=a^5b \cdot ab^5 \equiv 5(ab^5) \pmod 9 \Rightarrow ab^5 \equiv 2 \pmod 9 \Rightarrow ab^5+3 \equiv               5 \pmod 9$

which is not possible. Similarly, if $a^5b \equiv 7 \pmod 9$ then, 

          $(ab)^6=a^5b \cdot ab^5 \equiv 7(ab^5) \pmod 9 \Rightarrow ab^5 \equiv 4 \pmod 9 \Rightarrow ab^5+3 \equiv              7 \pmod 9$

which is not possible. So, no such integers.

-Lakshya Pamecha

Note

After you get that $a^5 b \equiv 5, 6, \text{or} 7 \pmod{9}$, you can also bash by listing all possible residues for $a^5$ and their corresponding values for $b$. At that point, you can easily see that all the solutions for $a$ and $b$ do not work in the other equation, meaning that there are no solutions that satisfy both equations.

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=2013_USAJMO_Problems/Problem_1&oldid=219170"