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

Post a Comment

Popular posts from this blog

LMAO Revenge

Continuing the tradition of past years, our seniors at the Indian IMO camp(an unofficial one happened this year) once again conducted LMAO, essentially ELMO but Indian. Sadly, only those who were in the unofficial IMOTC conducted by Pranav, Atul, Sunaina, Gunjan and others could participate in that. We all were super excited for the problems but I ended up not really trying the problems because of school things and stuff yet I solved problem 1 or so did I think. Problem 1:  There is a   grid of real numbers. In a move, you can pick any real number  ,  and any row or column and replace every entry   in it with  .  Is it possible to reach any grid from any other by a finite sequence of such moves? It turned out that I fakesolved and oh my god I was so disgusted, no way this proof could be false and then when I was asked Atul, it turns out that even my answer was wrong and he didn't even read the proof, this made me even more angry and guess wha...
2 comments
Read more

Functional Equations 101

Let's get to the math:  Let there be two sets $X$ and $Y$. A function  from $X$ to $Y$ denoted as $f \colon X \to Y$ is assigning a value in $Y$ for every element in $X$. We say that $X$ is the domain of the function $f$ and $Y$ is the range.  A function $f \colon X \to y$ is said to be injective if $f(x) = f(x^{\prime}) \implies x = x^{\prime}$ To put it in a more abstract way, if there is some $a \in Y$ then there is at most one $b \in X$ such that $f(b) = a$ holds true.  A function is said to be surjective when for any $a \in Y$ there is at least one $b \in X$ such that $f(b) = a$ holds true.  A function is bijective if for every $a \in Y$ there is exactly one $b \in X$ such that $f(b) = x$. Bijective functions are basically functions which are both injective and surjective.  Bonus: A function $f \colon X \to X$ is known as an involution if $f(f(x)) = x \; \forall  x \in X$  As an exercise, the readers should try to prove that every function th...
Post a Comment
Read more

The importance of "intuition" in geometry

Hii everyone! Today I will be discussing a few geometry problems in which once you "guess" or "claim" the important things, then the problem can easily be finished using not-so-fancy techniques (e.g. angle chasing, power-of-point etc. Sometimes you would want to use inversion or projective geometry but once you have figured out that some particular synthetic property should hold, the finish shouldn't be that non trivial) This post stresses more about intuition rather than being rigorous. When I did these problems myself, I used freehand diagrams (not geogebra or ruler/compass) because I feel that gives a lot more freedom to you. By freedom, I mean, the power to guess. To elaborate on this - Suppose you drew a perfect  diagram on paper using ruler and compass, then you would be too rigid on what is true in the diagram which you drew. But sometimes that might just be a coincidence. e.g. Let's say a question says $D$ is a random point on segment $BC$, so maybe ...
1 comment
Read more