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 "2015 USAMO Problems/Problem 5"

m (→‎Solution)
m (→‎Another Solution: + 2)
Line 17: Line 17:
 
~BealsConjecture
 
~BealsConjecture
  
−
===Another Solution===
+
===Solution 2===
  
 
A more conventional approach, using proof by contradiction:
 
A more conventional approach, using proof by contradiction:

Revision as of 13:55, 4 January 2016

Problem

Let $a, b, c, d, e$ be distinct positive integers such that $a^4 + b^4 = c^4 + d^4 = e^5$. Show that $ac + bd$ is a composite number.

Solution 1

Note: This solution is definitely not what the folks at MAA intended, but it works!

Look at the statement $a^4+b^4=e^5$. This can be viewed as a special case of Beal's Conjecture (http://en.wikipedia.org/wiki/Beal%27s_conjecture), stating that the equation $A^x+B^y=C^z$ has no solutions over positive integers for $gcd(a, b, c) = 1$ and $x, y, z > 2$. This special case was proven in 2009 by Michael Bennet, Jordan Ellenberg, and Nathan Ng, as $(x, y, z) = (2, 4, n)$. This case $a^4+b^4=e^5$ is obviously contained under that special case, so $a$ and $b$ must have a common factor greater than $1$.

Call the greatest common factor of $a$ and $b$ $f$. Then $a = f \cdot a_1$ for some $a_1$ and likewise $b = f \cdot b_1$ for some $b_1$. Then consider the quantity $ac+bd$.

$ac+bd = f \cdot a_1 \cdot c + f \cdot b_1 \cdot d = f\cdot(a_1 \cdot c + b_1 \cdot d)$.

Because $c$ and $d$ are both positive, $(a_1 \cdot c + b_1 \cdot d) > 1$, and by definition $f > 1$, so $ac+bd$ is composite.

~BealsConjecture

Solution 2

A more conventional approach, using proof by contradiction:

Without loss of generality, assume $a>d$

Since $a^4 +b^4=c^4+d^4$, It is obvious that $b<c$

We construct the equation $(a^4 +b^4)c^2d^2-(c^4+d^4)a^2b^2=(a^2c^2-b^2d^2)(a^2d^2-b^2c^2)$ (the right side is the factorization of the left) Which factors into: $e^5(cd-ab)(cd+ab)=(ac-bd)(ac+bd)(ad-bc)(ad+bc)$ (by using $a^4 +b^4=c^4+d^4=e^5$ and factoring)

If $ac-bd$ or $ad-bc$ equal zero, then $a:b$ equals $c:d$ or $d:c$ respectively, which is impossible because $a^4 +b^4=c^4+d^4$ and because $a,b,c,d,e$ are distinct. Therefore the right side of the equation above is non-zero and the left side must be divisible by $ac+bd$

If $ac+bd$ were prime,

We have $ac+bd-(cd+ab)=(a-d)(c-b)>0$

Which means that $ac+bd>cd+ab>cd-ab$ and neither $cd+ab$ nor $cd-ab$ can be multiples of $ac+bd$ meaning $e$ must be a multiple of $ac+bd$ and $e=k(ac+bd)$ for some integer $k$

But clearly this is impossible since $(k(ac+bd))^5>a^4+b^4$.

Therefore, by contradiction, $ac+bd$ is composite.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2015_USAMO_Problems/Problem_5&oldid=74308"