2
$\begingroup$

This question comes from a Chinese high school olympiad training program. It seems remarkably more difficult (and indeed, interesting!) than all other problems arising in the same program, especially since an elementary (high-school level) solution is probably available.

Show that there exists integers $a,b,c,d,e>2018$ so that the equation $$a^2+b^2+c^2+d^2+e^2+65=abcde$$ is satisfied.

For what it's worth, here's what I have tried. Rewriting the equation as a quadratic polynomial in $a$, $$a^2-(bcde)a+b^2+c^2+d^2+e^2+65=0.$$ For there to be integer solutions, the discriminant must be a perfect square. Hence $$ b^2c^2d^2e^2-4b^2-4c^2-4d^2-4e^2-4\cdot5\cdot13=n^2.$$ I don't however see how I can solve this equation, especially due to the large number of unknowns. Any ideas?


Edit: Ivan Neretin presents an excellent answer by Vieta Jumping, which I'm sure will yield results. However, the training program I mentioned has not discussed such advanced tactics as Vieta Jumping yet, and only covered $\gcd$, $\operatorname{lcm}$, factorisation of polynomials, discriminants, modular arithmetic, divisibility and quadratic residues. Hence despite Ivan's excellent solution, I would still be extremely appreciative of a more elementary solution.

$\endgroup$
  • $\begingroup$ Why is $abcde$ not orders of magnitude greater than the left hand side of the equation? If $a, b, c, d, e > 2018$ then the left hand is about $10^7$ whereas the right hand side should be about $10^{16}$, no? $\endgroup$ – stuart stevenson Nov 26 '18 at 23:00
  • 2
    $\begingroup$ @stuartstevenson: Only if all of $a,b,c,d,e$ are similarly-sized. $\endgroup$ – Micah Nov 26 '18 at 23:05
  • $\begingroup$ @Micah So you're saying that $a$, for instance, is orders of magnitude greater than $e$ assuming $a \geq b \geq c \ldots$? $\endgroup$ – stuart stevenson Nov 26 '18 at 23:10
  • 1
    $\begingroup$ @stuartstevenson Yes, we can have that. If we set $b=c=d=e$ for example we have a quadratic in $a$ which clearly yields a solution. The same is true for any other fixed values of $b,c,d,e$; we will always have a solution for $a$, even if orders of magnitude larger. The question does not care about the relative sizes of $a,b,c,d,e$ at all. $\endgroup$ – YiFan Nov 26 '18 at 23:13
  • 1
    $\begingroup$ Following Ivan Neretin's answer, I get following monstrous solution: $$\begin{align} a &= 7138\\ b &= 16988437\\ c &= 72151760667066\\ d &= 1041175313471572184867943319\\ e &= 9109630532627114315851511163018235051842553960810405 \end{align} $$ $\endgroup$ – achille hui Nov 26 '18 at 23:18
6
$\begingroup$

You are supposed to bruteforce or guess $(a,b,c,d,e)=(1,2,3,4,5)$ or any other small solution, and then go up by Vieta jumping. That is, once you have a solution, you rewrite it as a quadratic polynomial in $a$ (just like you did), and since one root is integer, so is the other. Then you do the same to $b,\;c...$ and repeat until the roots are big enough.

$\endgroup$
  • 3
    $\begingroup$ great answer, I tried it out and got a=9109630532627114315851511163018235051842553960810405,b=1041175313471572184867943319,c=7138,d=16988437,e=72151760667066; $\endgroup$ – miracle173 Nov 26 '18 at 23:18
  • $\begingroup$ Unfortunately the training program has not covered Vieta Jumping yet; it is at a much more elementary level (see the question edit). I'll accept this great answer if none else comes by after a day, but meanwhile, are you aware of a more elementary solution? $\endgroup$ – YiFan Nov 26 '18 at 23:28
  • $\begingroup$ @YiFan Maybe you should not use Vieta Jumping but only the fact that $x^2+px+q=(x-x_1)(x-x_2)$ if $x_1$ and $x_2$ are the solutions of $x^2+px+q=0$ $\endgroup$ – miracle173 Nov 26 '18 at 23:46
  • $\begingroup$ @miracle173 I'm aware of that fact, but how does that help? $\endgroup$ – YiFan Nov 27 '18 at 0:00
  • 4
    $\begingroup$ @YiFan If $(a,b,c,d,e)$ is a solution with $0 < a < b < c < d < e$, then $(b,c,d,e,bcde-a)$ is another solution with $0 < b < c < d < e < bcde - a$. Start from the seed solution $(1,2,3,4,5)$, this allow us to construct a sequence of solutions whose smallest member is increasing. I think this is something the kids can understand. $\endgroup$ – achille hui Nov 27 '18 at 0:15
1
$\begingroup$

Here is the output of the Maxima commands I used to calculate a solution according to Ivan Neretin's answer.

(%i2) ev(x^2-b*c*d*e*x+b^2+c^2+d^2+e^2+65,x = 1,b = 2,c = 3,d = 4,e = 5)

(%o2)                                  0

(%i3) ev(solve(x^2-b*c*d*e*x+b^2+c^2+d^2+e^2+65,x),b = 2,c = 3,d = 4,e = 5)

(%o3)                          [x = 1, x = 119]

(%i4) ev(solve(x^2-b*c*d*e*x+b^2+c^2+d^2+e^2+65,x),b = 119,c = 3,d = 4,e = 5)

(%o4)                          [x = 7138, x = 2]

(%i5) ev(solve(x^2-b*c*d*e*x+b^2+c^2+d^2+e^2+65,x),b = 119,c = 7138,d = 4,e

                                                                            = 5)

(%o5)                        [x = 3, x = 16988437]

(%i6) ev(solve(x^2-b*c*d*e*x+b^2+c^2+d^2+e^2+65,x),b = 119,c = 7138,

         d = 16988437,e = 5)

(%o6)                     [x = 72151760667066, x = 4]

(%i7) ev(solve(x^2-b*c*d*e*x+b^2+c^2+d^2+e^2+65,x),b = 119,c = 7138,

         d = 16988437,e = 72151760667066)

(%o7)              [x = 1041175313471572184867943319, x = 5]

(%i8) ev(solve(x^2-b*c*d*e*x+b^2+c^2+d^2+e^2+65,x),

         b = 1041175313471572184867943319,c = 7138,d = 16988437,

         e = 72151760667066)

(%o8) [x = 9109630532627114315851511163018235051842553960810405, x = 119]

(%i9) ev(x^2-b*c*d*e*x+b^2+c^2+d^2+e^2+65,

         x = 9109630532627114315851511163018235051842553960810405,

         b = 1041175313471572184867943319,c = 7138,d = 16988437,

         e = 72151760667066)

(%o9)                                  0
$\endgroup$
1
$\begingroup$

This expands upon @Ivan Neretin 's answer

This is what is meant by Vieta jumping, when it comes to this problem--we can use Vieta jumping to prove the following claim:

Proposition 1: For any $A \in \mathbb{Z}^+$ there is a solution $(a,b,c,d,e)$; $a,b,c,d,e \in \mathbb{Z}^+$ to the equation $a^2+b^2+c^2+d^2+e^2+65 = abcde$ such that $A \leq \min\{a,b,c,d,e\}$.

Proof: We first claim the following:

Claim 1: Let us suppose that there is a solution $a^2+b^2+c^2+d^2+e^2+65=120$; $a,b,c,d,e \in \mathbb{Z}^+$, and let us assume WLOG that $a= \min\{a,b,c,d,e\}$. Then there is a solution $(a',b',c',d',e')$; $a',b',c',d',e' \in \mathbb{Z}^+$ s.t. $a'>a$ and $b'=b,c'=c,d'=d,e'=e$.

[Proof of Claim 1: Indeed, iff there exists an integer $a'> a$ is that satisfies the following:

$a'^2 + (b^2+c^2+d^2+e^2)+65 > a'(bcde)$.

Then Claim 1 will follow. However, the above is a quadratic equation in $a'$ of the form $a'^2 - xa' + z$; both $x$ and $z$ positive integers, that has at least one integer solution, namely $a$, and so the other solution is an integer; as $z$ is at least $b^2+c^2+d^2+e^2+65$ $> 4a^2$ and $aa'=z$ with $a$ positive it follows that $a'$ must be strictly greater than $4a$. So indeed Claim 1 does follow. $\surd$ ]

We note that Proposition 1 follows immediately from Claim 1, and the existence of at least one solution $(a_0,b_0,c_0,d_0,e_0); a_0,b_0,c_0,d_0,e_0 \in \mathbb{Z}^+$ such that the equation $a_0^2+b_0^2+c_0^2+d_0^2+e_0^2+65 = a_0b_0c_0d_0e_0$ holds; namely $(a_0,b_0,c_0,d_0,e_0) =(1,2,3,4,5)$. $\surd$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.