Maths Olympiad Prep

Library / /31 of 43

Number theory Difficulty 6.1 National Olympiad Prove it JBMO

Problem:
Find all positive integers nn such that the equation y2+xy+3x=n(x2+xy+3y)y^{2}+x y+3 x=n\left(x^{2}+x y+3 y\right) has at least a solution (x,y)(x, y) in positive integers.

Solution

Solution:
Clearly for n=1n=1, each pair (x,y)(x, y) with x=yx=y is a solution. Now, suppose that n>1n>1 which implies xyx \neq y. We have
0<n1=y2+xy+3xx2+xy+3y1=(x+y3)(yx)x2+xy+3y. 0 < n-1 = \frac{y^{2}+x y+3 x}{x^{2}+x y+3 y}-1 = \frac{(x+y-3)(y-x)}{x^{2}+x y+3 y}.
Since x+y3x+y \geq 3, we conclude that x+y>3x+y>3 and y>xy>x. Take d=gcd(x+y3, x2+xy+3y)d=\operatorname{gcd}(x+y-3,\ x^{2}+x y+3 y). Then dd divides x2+xy+3yx(x+y3)=3(x+y)x^{2}+x y+3 y-x(x+y-3)=3(x+y). Then dd also divides 3(x+y)3(x+y3)=93(x+y)-3(x+y-3)=9, hence d{1,3,9}d \in\{1,3,9\}. As
n1=x+y3d(yx)x2+xy+3yd n-1=\frac{\frac{x+y-3}{d}(y-x)}{\frac{x^{2}+x y+3 y}{d}}
and gcd(x+y3d, x2+xy+3yd)=1\operatorname{gcd}\left(\frac{x+y-3}{d},\ \frac{x^{2}+x y+3 y}{d}\right)=1, it follows that x2+xy+3yd\frac{x^{2}+x y+3 y}{d} divides yxy-x, which leads to
x2+xy+3ydydxx2+dx(d3x)y. x^{2}+x y+3 y \leq d y-d x \Leftrightarrow x^{2}+d x \leq (d-3-x) y.
It is necessary that d3x>0d>3d-3-x>0 \Rightarrow d>3, therefore d=9d=9 and x<6x<6. Take x+y3=9k, kNx+y-3=9 k,\ k \in \mathbb{N}^{*} since dx+y3d \mid x+y-3 and we get y=9k+3xy=9 k+3-x. Hence
n1=k(9k+32x)k(x+3)+1. n-1=\frac{k(9 k+3-2 x)}{k(x+3)+1}.
Because kk and k(x+3)+1k(x+3)+1 are relatively prime, the number t=9k+32xk(x+3)+1t=\frac{9 k+3-2 x}{k(x+3)+1} must be integer for some positive integers x<6x<6. It remains to consider these values of xx:

1) For x=1x=1, then t=9k+14k+1t=\frac{9 k+1}{4 k+1} and since 1<t<31<t<3, we get t=2, k=1, y=11t=2,\ k=1,\ y=11, so n=3n=3.

2) For x=2x=2, then t=9k15k+1t=\frac{9 k-1}{5 k+1} and since 1<t<21<t<2, there are no solutions in this case.

3) For x=3x=3, then t=9k36k+1t=\frac{9 k-3}{6 k+1} and since 1t<21 \neq t<2, there are no solutions in this case.

4) For x=4x=4, then t=9k57k+1<2t=\frac{9 k-5}{7 k+1}<2, i.e. t=1t=1 which leads to k=3, y=26k=3,\ y=26, so n=4n=4.

5) For x=5x=5, then t=9k78k+1<2t=\frac{9 k-7}{8 k+1}<2, i.e. t=1t=1 which leads to k=8, y=70k=8,\ y=70, so n=9n=9.

Finally, the answer is n{1,3,4,9}n \in\{1,3,4,9\}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.