4
$\begingroup$

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.

Thanks in advance!

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

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.

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

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – JoshuaZ Sep 7 '19 at 2:09
  • $\begingroup$ That said, it seems like the core of your idea can be made to work. See my answer. $\endgroup$ – JoshuaZ Sep 7 '19 at 2:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.