MHB Can You Prove the GCD Inequality for Natural Numbers?

  • Thread starter Thread starter lfdahl
  • Start date Start date
  • Tags Tags
    Gcd Inequality
AI Thread Summary
The discussion revolves around proving the inequality involving the greatest common divisor (GCD) for natural numbers a and b, where b is greater than a. The inequality states that the sum of two fractions, involving the product of a and b divided by their GCD, and the product of (a+1) and (b+1) divided by their GCD, is greater than or equal to a specific expression involving the square root of the difference between b and a. Participants share various approaches to proving this inequality, highlighting different mathematical techniques and insights. The conversation emphasizes the importance of understanding GCD properties in relation to inequalities. The thread concludes with appreciation for contributions and alternative methods presented by participants.
lfdahl
Gold Member
MHB
Messages
747
Reaction score
0
Prove, that for all natural numbers, $a$ and $b$, with $b > a$:

\[\frac{ab}{(a,b)}+\frac{(a+1)(b+1)}{(a+1,b+1)}\geq \frac{2ab}{\sqrt{b-a}}\]

where $(m,n)$ denotes the greatest common divisor of the natural numbers $m$ and $n$.
 
Mathematics news on Phys.org
lfdahl said:
Prove, that for all natural numbers, $a$ and $b$, with $b > a$:

\[\frac{ab}{(a,b)}+\frac{(a+1)(b+1)}{(a+1,b+1)}\geq \frac{2ab}{\sqrt{b-a}}\]

where $(m,n)$ denotes the greatest common divisor of the natural numbers $m$ and $n$.
let $A=\dfrac{ab}{(a,b)}+\dfrac{(a+1)(b+1)}{(a+1,b+1)}$
$B=\dfrac{2ab}{\sqrt{b-a}}$
using $a\times b=(a,b)\times [a,b]$
where $(a,b)$ denotes the greatest common divisor of the natural numbers $a$ and $b$
and $[a,b]$ denotes the least common multiple of the natural numbers $a$ and $b$
we have $min(A)=b+b+1\leq A=[a,b]+[a+1,b+1]\leq ab+(a+1)(b+1)$
$=2ab+a+b+1=max(A)$
$B\leq 2ab=max(B)$
if we can find a solution $min(A)\geq max(B)$
that is to find solution $2b+1\geq 2ab$ then we have the proof
in this case $a=1,b>a$
in general we may set $b-a=k>0$
to find $\sqrt k(2b+1)\geq 2ab$
we get $\sqrt k=a,or \,\, k=a^2$
 
Last edited:
Albert said:
let $A=\dfrac{ab}{(a,b)}+\dfrac{(a+1)(b+1)}{(a+1,b+1)}$
$B=\dfrac{2ab}{\sqrt{b-a}}$
using $a\times b=(a,b)\times [a,b]$
where $(a,b)$ denotes the greatest common divisor of the natural numbers $a$ and $b$
and $[a,b]$ denotes the least common multiple of the natural numbers $a$ and $b$
we have $min(A)=b+b+1\leq A=[a,b]+[a+1,b+1]\leq ab+(a+1)(b+1)$
$=2ab+a+b+1=max(A)$
$B\leq 2ab=max(B)$
if we can find a solution $min(A)\geq max(B)$
that is to find solution $2b+1\geq 2ab$ then we have the proof
in this case $a=1,b>a$
in general we may set $b-a=k>0$
to find $\sqrt k(2b+1)\geq 2ab$
we get $\sqrt k=a,or \,\, k=a^2$

Thankyou, Albert for your approach to the problem. Well done.

Here´s another approach:

By applying the AM-GM inequality we get:
\[\frac{ab}{(a,b)}+\frac{(a+1)(b+1)}{(a+1,b+1)}\geq 2 \sqrt{\frac{a(a+1)b(b+1)}{(a,b)(a+1,b+1)}} > \frac{2ab}{\sqrt{(a,b)(a+1,b+1)}}\]
In order to complete the solution, we now show that:
\[b-a \ge (a,b)(a+1,b+1)\]
Indeed, $(a,b)$ and $(a+1,b+1)$ both divide $b-a$, since the greatest common divisor of two
numbers also divides their difference. On the other hand, $(a,b)$ and $(a+1,b+1)$ are coprimes.
Therefore the product $(a,b)(a+1,b+1)$ divides $b-a$. Hence the inequality is proved.
 
Seemingly by some mathematical coincidence, a hexagon of sides 2,2,7,7, 11, and 11 can be inscribed in a circle of radius 7. The other day I saw a math problem on line, which they said came from a Polish Olympiad, where you compute the length x of the 3rd side which is the same as the radius, so that the sides of length 2,x, and 11 are inscribed on the arc of a semi-circle. The law of cosines applied twice gives the answer for x of exactly 7, but the arithmetic is so complex that the...
Is it possible to arrange six pencils such that each one touches the other five? If so, how? This is an adaption of a Martin Gardner puzzle only I changed it from cigarettes to pencils and left out the clues because PF folks don’t need clues. From the book “My Best Mathematical and Logic Puzzles”. Dover, 1994.
Thread 'Imaginary Pythagoras'
I posted this in the Lame Math thread, but it's got me thinking. Is there any validity to this? Or is it really just a mathematical trick? Naively, I see that i2 + plus 12 does equal zero2. But does this have a meaning? I know one can treat the imaginary number line as just another axis like the reals, but does that mean this does represent a triangle in the complex plane with a hypotenuse of length zero? Ibix offered a rendering of the diagram using what I assume is matrix* notation...
Back
Top