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"

(Added page and kludgy solution)
 
m (→‎Another Solution: + 2)
(4 intermediate revisions by 3 users not shown)
Line 3: Line 3:
 
Let <math>a, b, c, d, e</math> be distinct positive integers such that <math>a^4 + b^4 = c^4 + d^4 = e^5</math>. Show that <math>ac + bd</math> is a composite number.
 
Let <math>a, b, c, d, e</math> be distinct positive integers such that <math>a^4 + b^4 = c^4 + d^4 = e^5</math>. Show that <math>ac + bd</math> is a composite number.
  
−
===Solution===
+
===Solution 1===
  
 
Note:  This solution is definitely not what the folks at MAA intended, but it works!
 
Note:  This solution is definitely not what the folks at MAA intended, but it works!
  
−
Look at the statement <math>a^4+b^4=e^5</math>.  This can be viewed as a special case of [[http://en.wikipedia.org/wiki/Beal%27s_conjecture|Beal's Conjecture]], stating that the equation <math>A^x+B^y=C^z</math> has no solutions over positive integers for <math>gcd(a, b, c) = 1</math> and <math>x, y, z > 2</math>. This special case was proven in 2009 by Michael Bennet, Jordan Ellenberg, and Nathan Ng, as <math>(x, y, z) = (2, 4, n)</math>.  This case <math>a^4+b^4=e^5</math> is obviously contained under that special case, so <math>a</math> and <math>b</math> must have a common factor greater than <math>1</math>.   
+
Look at the statement <math>a^4+b^4=e^5</math>.  This can be viewed as a special case of Beal's Conjecture (http://en.wikipedia.org/wiki/Beal%27s_conjecture), stating that the equation <math>A^x+B^y=C^z</math> has no solutions over positive integers for <math>gcd(a, b, c) = 1</math> and <math>x, y, z > 2</math>. This special case was proven in 2009 by Michael Bennet, Jordan Ellenberg, and Nathan Ng, as <math>(x, y, z) = (2, 4, n)</math>.  This case <math>a^4+b^4=e^5</math> is obviously contained under that special case, so <math>a</math> and <math>b</math> must have a common factor greater than <math>1</math>.   
  
 
Call the greatest common factor of <math>a</math> and <math>b</math> <math>f</math>.  Then <math>a = f \cdot a_1</math> for some <math>a_1</math> and likewise <math>b = f \cdot b_1</math> for some <math>b_1</math>.  Then consider the quantity <math>ac+bd</math>.   
 
Call the greatest common factor of <math>a</math> and <math>b</math> <math>f</math>.  Then <math>a = f \cdot a_1</math> for some <math>a_1</math> and likewise <math>b = f \cdot b_1</math> for some <math>b_1</math>.  Then consider the quantity <math>ac+bd</math>.   
Line 13: Line 13:
 
<math>ac+bd = f \cdot a_1 \cdot c + f \cdot b_1 \cdot d = f\cdot(a_1 \cdot c + b_1 \cdot d)</math>.
 
<math>ac+bd = f \cdot a_1 \cdot c + f \cdot b_1 \cdot d = f\cdot(a_1 \cdot c + b_1 \cdot d)</math>.
  
−
Because <math>b</math> and <math>d</math> are both positive, <math>(a_1 \cdot c + b_1 \cdot d) > 1</math>, and by definition <math>f > 1</math>, so <math>ac+bd</math> is composite.   
+
Because <math>c</math> and <math>d</math> are both positive, <math>(a_1 \cdot c + b_1 \cdot d) > 1</math>, and by definition <math>f > 1</math>, so <math>ac+bd</math> is composite.   
  
 
~BealsConjecture
 
~BealsConjecture
 +
 +
===Solution 2===
 +
 +
A more conventional approach, using proof by contradiction:
 +
 +
Without loss of generality, assume <math>a>d</math>
 +
 +
Since <math>a^4 +b^4=c^4+d^4</math>, It is obvious that <math>b<c</math>
 +
 +
We construct the equation <math>(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)</math> (the right side is the factorization of the left) Which factors into: <math>e^5(cd-ab)(cd+ab)=(ac-bd)(ac+bd)(ad-bc)(ad+bc)</math> (by using <math>a^4 +b^4=c^4+d^4=e^5</math> and factoring)
 +
 +
If <math>ac-bd</math> or <math>ad-bc</math> equal zero, then <math>a:b</math> equals <math>c:d</math> or <math>d:c</math> respectively, which is impossible because <math>a^4 +b^4=c^4+d^4</math> and because <math>a,b,c,d,e</math> are distinct. Therefore the right side of the equation above is non-zero and the left side must be divisible by <math>ac+bd</math>
 +
 +
If <math>ac+bd</math> were prime,
 +
 +
We have <math>ac+bd-(cd+ab)=(a-d)(c-b)>0</math>
 +
 +
Which means that  <math>ac+bd>cd+ab>cd-ab</math> and neither <math>cd+ab</math> nor <math>cd-ab</math> can be multiples of <math>ac+bd</math> meaning <math>e</math> must be a multiple of <math>ac+bd</math> and <math>e=k(ac+bd)</math> for some integer <math>k</math>
 +
 +
But clearly this is impossible since <math>(k(ac+bd))^5>a^4+b^4</math>.
 +
 +
Therefore, by contradiction, <math>ac+bd</math> is composite.

Revision as of 14: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"