Maths Olympiad Prep

Library / /29 of 65

Number theory Difficulty 6.1 National Olympiad Prove it Bulgaria

Problem:

Let aa, bb and cc be positive integers such that abab divides c(c2c+1)c\left(c^{2}-c+1\right) and a+ba+b is divisible by c2+1c^{2}+1. Prove that the sets {a,b}\{a, b\} and {c,c2c+1}\left\{c, c^{2}-c+1\right\} coincide.

Solution

Solution:

We shall use the following lemma.

Lemma. Let xx, yy and nn be positive integers such that xyx+y>n\frac{xy}{x+y} > n. Then
xyx+yn+1n2+2n+2 \frac{xy}{x+y} \geq n + \frac{1}{n^{2} + 2n + 2}
with equality if and only if {x,y}={n+1,n2+n+1}\{x, y\} = \left\{n+1, n^{2}+n+1\right\}.

Proof of the lemma. Since xy>n(x+y)xy > n(x+y), we have xy=n(x+y)+rxy = n(x+y) + r, where rr is a positive integer. Then (xn)(yn)=n2+r(x-n)(y-n) = n^{2} + r, which implies that x>nx > n and y>ny > n. Set x=n+d1x = n + d_{1} and y=n+d2y = n + d_{2}. Then d1d2=n2+rd_{1} d_{2} = n^{2} + r. Now using the inequalities rA+r1A+1\frac{r}{A+r} \geq \frac{1}{A+1} and d1+d21+n2+rd_{1} + d_{2} \leq 1 + n^{2} + r (the latter follows from d1+d21+d1d2d_{1} + d_{2} \leq 1 + d_{1} d_{2}), we get
xyx+y=n2+d1d2+n(d1+d2)2n+d1+d2=n+r2n+d1+d2n+r2n+n2+1+rn+1n2+2n+2 \begin{aligned} \frac{xy}{x+y} &= \frac{n^{2} + d_{1} d_{2} + n(d_{1} + d_{2})}{2n + d_{1} + d_{2}} = n + \frac{r}{2n + d_{1} + d_{2}} \\ &\geq n + \frac{r}{2n + n^{2} + 1 + r} \geq n + \frac{1}{n^{2} + 2n + 2} \end{aligned}
Note that the equality is attained if and only if {x,y}={n+1,n2+n+1}\{x, y\} = \left\{n+1, n^{2}+n+1\right\}. This completes the proof of the lemma.

The condition of the problem implies that c(c2c+1)=pabc\left(c^{2}-c+1\right) = p a b and a+b=q(c2+1)a+b = q\left(c^{2}+1\right), where pp and qq are positive integers. Therefore
c(c2c+1)c2+1=pqaba+b=xyx+y \frac{c\left(c^{2}-c+1\right)}{c^{2}+1} = \frac{pqab}{a+b} = \frac{xy}{x+y}
where x=pqax = pqa and y=pqby = pqb. Then
xyx+y=cc2c2+1=c1+1c2+1 \frac{xy}{x+y} = c - \frac{c^{2}}{c^{2}+1} = c-1 + \frac{1}{c^{2}+1}
whence xyx+y>c1\frac{xy}{x+y} > c-1. Now the lemma gives
xyx+yc1+1(c1)2+2(c1)+2=c1+1c2+1 \frac{xy}{x+y} \geq c-1 + \frac{1}{(c-1)^{2} + 2(c-1) + 2} = c-1 + \frac{1}{c^{2}+1}
Hence we have the case of equality and therefore
{x,y}={c,c2c+1} \{x, y\} = \left\{c, c^{2}-c+1\right\}
Since the numbers cc and c2c+1c^{2}-c+1 are coprime and x=pqax = pqa, y=pqby = pqb, it follows that p=q=1p = q = 1. Hence {a,b}={c,c2c+1}\{a, b\} = \left\{c, c^{2}-c+1\right\}.

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.