# How would you prove if $ab|(a+b)(a+b+1)$, then $(a,b) \leq \sqrt{a+b}$ for positive integers $a$ and $b$?

How would you prove if $$ab|(a+b)(a+b+1)$$, then $$(a,b) \leq \sqrt{a+b}$$ for positive integers $$a$$ and $$b$$?

My thoughts: I tried squaring both sides of $$(a,b) \leq \sqrt{a+b}$$ but don't know what to do with $$(a,b)^2$$ afterwards. I thought maybe using $$\sqrt{ab} \leq \sqrt{(a+b)(a+b+1)} = \sqrt{(a+b)^2 + (a+b)}$$ would help but I don't see how I could use it.

• @Dzoooks Could you please give a hint on how to use $(a,b)^2 \leq ab$? – Borna Ahmadzade Sep 7 '19 at 1:32

Assume that $$a$$ and $$b$$ are positive integers satisfying $$ab|(a+b)(a+b+1)$$. Set $$gcd(a,b)=x$$, and set $$a_x = a/x$$, and $$b_x=b/x$$. Note that $$xa_x = a$$ and $$xb_x=b$$. Note also that $$(a_x,b_x)=1.$$ Since $$ab|(a+b)(a+b+1)$$ one has $$x^2a_xb_x|(xa_x + xb_x)(xa_x + xb_x +1)$$ which implies that $$xa_xb_x|(a_x + b_x)(xa_x + xb_x +1).$$ Now note that $$gcd(x,xa_x + xb_x +1)=1$$ so the previous relation forces $$x|a_x+b_x$$. We have then $$x \leq a_x + b_x = \frac{a}{x} + \frac{b}{x}.$$ One has then from clearing $$x$$ in the denominator $$x^2 \leq a+b$$ which implies the desired inequality.

Note that from a similar argument you can actually get a lower bound on $$x$$ and obtain that $$x \geq \sqrt{\frac{ab}{a+b+1}}.$$ So the actual possible range for the gcd is pretty tiny.

I'm highly curious where this problem came from. It isn't one I've seen before.

• It's actually from a Maryam Mirzakhani book(which unfortunately is only available in my language, Persian) about number theory for IMO – Borna Ahmadzade Sep 7 '19 at 13:17

Let $$d=gcd(a,b)$$. Then, $$d|a+b$$ and hence $$gcd(d,a+b+1)=1$$.

This gives $$gcd(d^2,a+b+1)=1$$.

Now, you have $$d^2|ab|(a+b)(a+b+1) \, \mbox{ and }\, gcd(d^2, a+b+1)=1 \Rightarrow d^2|a+b$$

This gives you what you want.

Suppose that $$(a,b)=x$$, then we have $$x^2 · \frac{ab}{x^2}|(a+b)(a+b+1)$$ Since we have (a+b,a+b+1)=1, we can say that $$x^2|(a+b)$$ or $$x^2|(a+b+1)$$. If there exists a number t such that $$t^2|(a+b)$$ and $$\frac{x^2}{t^2}|(a+b+1)$$ (or reversely) then $$(a,b)=tx$$ which contradicts to the former assumption, then we have the conclusion by rooting($$\sqrt{x^2}$$). Because this is my first time to answer question, there might be some mistakes in describing or showing the formula, I still hope that my answer can help you to solve this problem.

• I don't think this works. In particular, one cannot conclude that either $x^2|a+b$ or $x^2 |a+b+1$. This would be valid if $x$ was a power of a prime, but there's no reason that it couldn't split pieces up this way. – JoshuaZ Sep 7 '19 at 2:09
• That said, it seems like the core of your idea can be made to work. See my answer. – JoshuaZ Sep 7 '19 at 2:28