USAMO 2015 P5

For discussing Olympiad Level Number Theory problems
User avatar
Kazi_Zareer
Posts:86
Joined:Thu Aug 20, 2015 7:11 pm
Location:Malibagh,Dhaka-1217
USAMO 2015 P5

Unread post by Kazi_Zareer » Sun Dec 25, 2016 11:35 am

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

Can't solve it properly :( :( . Any help will be appreciated! :)

Thanks You!
We cannot solve our problems with the same thinking we used when we create them.

User avatar
ahmedittihad
Posts:181
Joined:Mon Mar 28, 2016 6:21 pm

Re: USAMO 2015 P5

Unread post by ahmedittihad » Sun Jan 01, 2017 1:22 am

Not my solution

Clearly $ac+bd>2$, so supposed for sake of contradiction that $ac+bd=p$, some odd prime.

Assume without loss of generality that $a>c,$ or otherwise we could switch $a$ with $c$ and $b$ with $d$. So $a^4>c^4=a^4+b^4-d^4$ implying $b^4<d^4$ and $b<d$.

Now note $a^4-c^4=d^4-b^4$ so
\[
(a^2-c^2)(a^2+c^2)(d^2-b^2)(d^2+b^2)
\]
Lemma: If $f,g,h,i$ are positive integers satisfying $fg=hi$, then there exist positive integers $w,x,y,z$ such that
\[
f=wx,g=yz,h=wy,i=xz
\]
Proof: This is well known, but a proof is included anyway.

Let $w=\gcd(f,h)$, and let $f=wx$,$h=wy$ for some relatively prime positive integers $x,y$. Now $fg=hi$ implies
\[
wxg=wyii
\]
so
\[
xg=yi
\]
Since $x,y$ are relatively prime,
\[
x\mid yi \Rightarrow x\mid i
\]
Let $z = \frac{i}{x}$, so now $i=zx$ and
\[
xg=yzx\Rightarrow g = yz
\]
so we have found $w,x,y,z$.

Apply the lemma to
\[
(a^2-c^2)(a^2+c^2)=(d^2-b^2)(d^2+b^2)
\]
We obtain $w,x,y,z$ so that
\[
wx=a^2-c^2,yz=a^2+c^2,wy=d^2-b^2,xz=d^2+b^2
\]

Solving these equations for $a^2,b^2,c^2,d^2$ yields.
\[
a^2=\frac{wx+yz}{2}
\]
\[
b^2=\frac{xz-wy}{2}
\]
\[
c^2=\frac{yz-wx}{2}
\]
\[
d^2=\frac{wy+xz}{2}
\]
so
\begin{align*}
a^2c^2-b^2d^2&=\left(\frac{wx+yz}{2}\right)\left(\frac{yz-wx}{2}\right)-\left(\frac{xz-wy}{2}\right)\left(\frac{wy+wz}{2}\right)\\
&=\frac{y^2z^2-w^2x^2-x^2z^2+w^2y^2}{4}\\
&=\frac{(w^2+z^2)(y^2-x^2)}{4}\\
&=\frac{(w^2+z^2)(y-x)(y+x)}{4}
\end{align*}
Factoring the left hand side yields
\begin{align}
(ac-bd)(ac+bd)=(ac-bd)p=\frac{(w^2+z^2)(y-x)(y+x)}{4}
\end{align}
Suppose we had $ac=bd$. This would imply $a^4c^4=b^4d^4$ so
\[
c^4(c^4+d^4)=c^4(a^4+b^4)=a^4c^4+b^4c^4=b^4d^4+b^4c^4=b^4(c^4+d^4)
\]
and $b^4=c^4$, contradicting distinctness.
So $ac-bd\neq 0$. In fact we can assume WLOG $ac-bd>0$, or we could switch $a$ with $d$ and $b$ with $c$. So $y>z$ as well.

$p$ is odd and divides the right hand side of $(1)$. So either $p\mid w^2+z^2$, $p\mid y-x$, or $p \mid y+x$. In each case we derive a contradiction.

Case 1: $p\mid w^2+z^2$.

Note that
\begin{align*}
e^5=a^4+b^4&=\left(\frac{wx+yz}{2}\right)^2+\left(\frac{xz-wy}{2}\right)^2\\
&=\frac{w^2x^2+y^2z^2+2wxyz+x^2z^2+w^2y^2-2wxyz}{4}\\
&=\frac{w^2x^2+y^2z^2+x^2z^2+w^2y^2}{4}\\
&=\frac{(w^2+z^2)(y^2+x^2)}{4}
\end{align*}
so $p \mid e^5$ (since $p$ is odd). Thus $p\mid e$ and $p^5\le e^5$. This implies
\[
(ac+bd)^5\le e^5=a^4+b^4
\]
but
\begin{align*}
(ac+bd)^5&\ge a^5c^5+5a^4c^4bc+5acb^4d^4+b^5d^4\\
&>5a^4c^4bd+5acb^4d^4\\
&>a^4+b^4
\end{align*}
which is a contradiction.

Case 2: $p\mid y-x$. Then
\begin{align*}
ac-bd&=\left(\frac{(w^2+z^2)(y+x)}{4}\right)\left(\frac{y-x}{p}\right)\\
&=(y+x)\left(\frac{w^2+z^2}{4}\right)
\end{align*}
Now if we had $w=z=1$, this would imply
\[
a^2=\frac{x+y}{2}=d^2
\]
a contradiction. So $w^2+z^2\ge 5>$, and
\[
ac-bd>y+x>y-x\ge p = ac+bd
\]
But this is clearly impossible for positive $a,b,c,d$.

Case 3: $p\mid y+x$

Note that
\begin{align*}
p&=ac+bd>c^2+b^2\\
&=\frac{xz-wy}{2}+\frac{yz-wx}{2}\\
&=\frac{(y+x)(z-w)}{2}
\end{align*}
Note $b^2+c^2>0$ so $z>w$.

If we had $z-w=1$, then this would imply $y+x=2(b^2+c^2)$. So $p\mid 2(b^2+c^2)$ implies $p\mid b^2+c^2$ since $p$ is odd. But $p>c^2+b^2$ as before, contradiction. Otherwise, $z-w\ge 2$, so
\[
p>c^2+b^2\ge y+x
\], which contradicts $p\mid y+z$.

In all cases, there is a contradiction, and $ac+bd$ is composite.
Frankly, my dear, I don't give a damn.

User avatar
Thanic Nur Samin
Posts:176
Joined:Sun Dec 01, 2013 11:02 am

Re: USAMO 2015 P5

Unread post by Thanic Nur Samin » Mon Jan 02, 2017 9:09 pm

For the sake of contradiction, let $ac+bd=p$ a prime. Now, we get,

$$a^4c^4 \equiv b^4d^4 (\text{mod } p)$$
$$(e^5-b^4)c^4 \equiv b^4(e^5-c^4) (\text{mod } p)$$
$$p|e^5(b^4-c^4)$$

Now, $p|e^5\Rightarrow p^5|a^4+b^4$ which is impossible for size reasons.

So, $p|(b^2+c^2)(b+c)(b-c)$

Clearly, for size reasons, the only case we need to deal with is $p|(b^2+c^2)\Rightarrow p|(ac+bd)^2+(ab-cd)^2$

So we get $p|ab-cd$.

The rest is left to the reader as an excercise.
Hammer with tact.

Because destroying everything mindlessly isn't cool enough.

Post Reply