Skip to main content

Friendly numbers and infinite descent

Hey everyone, today we discuss two very cute ISL NTs! Hope you like it.

 ISL 2012 N4

ISL 2012 N4:An integer $a$ is called friendly if the equation $(m^2+n)(n^2+m)=a(m-n)^3$ has a solution over the positive integers.

a) Prove that there are at least $500$ friendly integers in the set ${ 1,2,\ldots ,2012}$.

b) Decide whether $a=2$ is friendly


Part A 

Claim: All $a \equiv 1 ( \mod 4)$  works for all $m=2n+1$

Proof: 

$$(4n^2+5n+1)(n+1)^2=a(n+1)^3$$

$$4n^2+n(5-a)+1-a=0$$

$$n=\frac{a-5 \pm \sqrt{a^2+6a+9}}{8}$$

$$=\frac {a-5 \pm a+3}{8}$$

$$= 1 or \frac{a-1}{4}$$


Therefore, we clearly have $500$ such working $n$.


Part B

Subclaim: If $p|m$, then $p|n$ also,$p|n$, then $p|=m$ for $p$ not equal to $3$ 

Claim: $V_p(m)=2V_p(n)$ or $V_p(n)=2V_p(m)$ for all  prime $p$, where $p$ divides $n$

Proof: 

$$(m^2+n)(n^2+m)=2(m-n)^3$$

$$0=m^3+m^2(-6n-n^2)+m(6n^2-n) -3n^3$$

Which implies that $m|3n^3$ and $n|m^3$

So, our subclaim is true.

Now, consider some prime $p$ such that $p|n$ which also implies that $p|m$ 

Case 1: $V_p(m)> V_p(n)$

$$V_p(m^2+n)=V_p(n)$$

$$V_p2(m-n)^3 \geq 3V_p(n)$$

Which implies that $V_p(n^2+m) \geq 2V_p(n)$ 

As such, $V_p(m)=V_p(n^2)=2V_p(n)$ 


Case 2: $V_p(n)= V_p(m)$ 

$$V_p(m^2+n)=V_p(n)$$

$$V_p(n^2+m)=V_p(n)$$

$$V_p(2(m-n)^3) \geq 3V_p(n) >2V_p(n) $$

Which is absurd, hence such a case cannot exist to begin with.

Therefore, our main claim is true 


Case 1: $3$ does not divide $m$ 

Observe that this directly implies that $m|n^2$ 

$$2m^3>2(m-n)^3 =(m^2+n)(n^2+m) >2m^3$$ 

Which is absurd 


Case 2: $3$ divides $m$ 

If $m=3n^2$

$$(9n^4+n)(10n^2)=2(3n^2-n)^3$$ 

$$90n^3+10=2(27n^3-27n^2+27n-1)$$

$$ \leq 2(27n^3)=54n^3$$


But this RHS is smaller than the LHS which is absurd, implying that there is no solution

If $m=\frac{3n^2}{2}$

$$(\frac{9n^2}{4}+n)(\frac{5n^2}{2}=2(\frac{3n^2}{2}-n)^3$$

$$45n^3+20=54n^3-108n^2+72-16$$

$$0=9n^3-108n^2+72n-36$$


Checking from $n=1$ to $n=12$, we observe that there is no $n$ satisfying the above equation 

Note that for the remaining cases $m\leq n^2$, which as we have resolved earlier fails due to size argument 

Therefore $a=2$ is not friendly.


Remark

The main motivation behind the solution in part A was to try and cancel out some factors on both sides of the equation so that it would be easier to find a solution. It just happened to be that $m=2n+1$ conveniently works. Part B seems much more motivated than Part A in my opinion. This is because for Part B, the main idea is that we have some divisibility conditions involving $m$ and $n$, from there we get some strict bounds on the primes that divide the two numbers. From there, we can proceed by some case whack and then bounding, which eventually finishes the problem.


ISL 2010 N3:

Find the smallest number $n$ such that there exist polynomials $f_1, f_2, \ldots , f_n$ with rational coefficients satisfying $$x^2+7 = f_1\left(x\right)^2 + f_2\left(x\right)^2 + \ldots + f_n\left(x\right)^2.$$


We claim that $n=5$ 

Construction: 

Set the 5 functions to be $x,2,1,1,1$

Claim: No 3 rational squares can sum to $7$

Proof: 

Suppose otherwise. Since we are considering rational numbers, we can instead consider proving the altered statement 

$$a^2+b^2+c^2=7d^2$$

Where $a,b,c,d$ are integers 

Subclaim:$a,b,c,d$ must all be even


Proof: 

If $d$ even, $a,b,c$ all even or $2$ odd, $1$ even 

Taking $\mod 4$, if $2$ odd $1$ even, the LHS $\equiv 2 (\mod 4)$ which is absurd 

If $d$ odd, $a,b,c$ must be $2$ even $1$ odd or all odd. 

If $2$ even $1$ odd, similarly take $\mod 4$ to force out a contradiction

If all odd, we take $\mod 8$. The LHS will be $\equiv 3(\mod 8)$ while the RHS $\equiv 7 (\mod 8)$, contradiction 

Now using our subclaim, we proceed by infinite descent to get that there are no solutions to $a,b,c$ , which proves our claim

Claim: $n \leq 4$ fails

Note that all $f_i(x)$ are of the form $a_ix+b_i$ 

This is because all the leading coefficients when squared are positive, so 

$$\deg (f_i(x))^2 \leq 2$$

$$\deg (f_i(x)) \leq 1$$

Observe that $n=1$ obviously fails 

$n=3$

Note $$b_1^2+b_2^2+b_3^2=7$$ 

Using our earlier claim, there are no rational solutions to this equation 

$n=2$

Observe that this is simply the $n=3$ case but with $b_1=0$, so there are naturally no solutions either 

$n=4$

WLOG let $f_1(x)=a_1x+b_1$ where $a_1$ is non-zero. Observe that this must exist or else there cannot be an $x^2$ term 

Now we set $x= \frac{b_1}{1-a_1}$

Observe that this will cause $x^2=f_1(\frac{b_1}{1-a_1})^2$

Therefore, we have $$f_2(\frac{b_1}{1-a_1})^2+f_3(\frac{b_1}{1-a_1})^2+f_4(\frac{b_1}{1-a_1})^2=7$$

Which does not have any solutions as we have previously mentioned

Remark

For this question, I think that getting $n=5$ is quite easy as one would try to "split" the polynomial up into $x^2$ and $7$, which essentially just boils the question down into how many rational squares does it take to form 7. I also feel like, it is not really hard to observe the degree of the various polynomials, $f(x)$ is at most 1. Then, it really boils down to showing that the sum of 3 rational squares cannot be 7 and personally I think this is really kind of the "leap of faith" in this problem. But if one is quite familiar with diophantine equations it is quite clear that infinite descent kills the question off almost immediately.

~Taeyoung

Comments

Popular posts from this blog

Constructions in Number Theory

Hi, I am Emon, a ninth grader, an olympiad aspirant, hailing from Kolkata. I love to do olympiad maths and do some competitive programming in my leisure hours, though I take it seriously. I had written INOI this year. Today, I would be giving you a few ideas on how to Construct in Number Theory . Well, so we shall start from the basics and shall try to dig deeper into it with the help of some important and well-known theorems and perhaps, some fancy ones as well. Okay, so without further delay, let's start off... What do we mean by "Constructions"? If noticed, you can see that you often face with some problems in olympiad saying, "... Prove that there exists infinitely many numbers satisfying the given conditions" or "... Prove that there exists a number satisfying the above conditions." These are usually the construction-problems .  For example, let's consider a trivial example : Problem. Prove that there exist infinitely many integers $a$ such th

EGMO solutions, motivations and reviews ft. Atul, Pranjal and Abhay

The  European Girls' Mathematical Olympiad a.k.a EGMO 2022 just ended. Congrats to Jessica Wan from USA, Taisiia Korotchenko, and Galiia Sharafetdinova for the perfect scores! Moreover, the Indian girls brought home 4 bronze medals! By far, this is the best result the EGMO India Team has ever achieved! To celebrate the brilliant result, here's a compilation of EGMO 2022 solutions and motivations written by my and everyone's favorite IMOTCer Atul ! And along with that, we also have reviews of each problem written by everyone's favorite senior, Pranjal !  These solutions were actually found by Atul, Pranjal,  and Abhay  during the 3-hour live solve. In the live solve, they solved all the 6 problems in 3 hours 😍!!! Okie Dokie, I think we should get started with the problems! Enjoy! Problem 1:  Let $ABC$ be an acute-angled triangle in which $BC<AB$ and $BC<CA$. Let point $P$ lie on segment $AB$ and point $Q$ lie on segment $AC$ such that $P \neq B$, $Q \neq C$ and

Q&A with experts about bashing

Heyy everyone! From the title, you can see that we are going to talk about  BASH.  Yesss, we are going to discuss whether you really need to learn bash or not?  Let me first introduce myself, I am Pranav Choudhary, a 10th grader from Haryana(India). I like to do geo and combo the most :PP. Oki so let's begin! For those of you who don't know what bashing is, lemme give you a brief introduction first. Bashing is basically a technique used to solve Geometry Problems. In general, when you try a geo problem you might think of angles, similarities, and some other techniques (e.g. Inversion, spiral similarity etc). All of which are called synthetic geometry. But sometimes people use various other techniques called "bash" to solve the same problems.  Now there are different kinds of bashing techniques, e.g. - Coordinate bash, Trig Bash, Complex bash, Barycentric Coordinates. Let me give you a brief introduction to each of them.  Coordinate Bash : You set one point as the orig