All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Inequality challenge (Posted on 2016-10-25)
Given two integers a and b such that:
I. a>b>1
ii. a+b divides ab+1
iii. a-b divides ab-1

Prove that a is less than b*sqrt(3).

 No Solution Yet Submitted by Ady TZIDON No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 re(2): Thoughts...Hints...Proof | Comment 3 of 4 |

Ady's hints imply that there are two lemmas to prove in order to complete the main proof.
Lemma 1: Prove b^2-1 must be divisible by a+b and a-b.
Lemma 2: Prove the greatest common divisor of a+b and a-b is either 1 or 2.

Lemma 1 proof:

Rewrite the identity as b*(a+b) - (ab+1).  The first term is divisible by a+b as implied by its factoring.  From statement ii the second term is divisible by a+b.  Therefore the entire expression is divisible by a+b.

Now rewrite the identity as -b*(a-b) + (ab-1).  The first term is divisible by a-b as implied by its factoring.  From statement iii the second term is divisible by a-b.  Therefore the entire expression is divisible by a-b.

The combination of these two conclusions then implies b^2-1 must be divisible by both a+b and a-b.  QED Lemma 1.

Note that Lemma 1 does not imply b^2-1 is divisible by the product (a+b)*(a-b), for example a=19,b=11 yields the fraction (121-1)/(30*8) = 120/240 = 1/2.  This is because the greatest common factor of a+b and a-b is doubly represented in the denominator but only singly represented in the numerator.  Now Lemma 2 comes into play.

Lemma 2 proof:
Let g be the greatest common divisor of a and b.  Then g is a factor of a+b and a*b.  a*b is coprime to a*b+1. g is a factor of a*b therefore g is coprime to a*b+1.

a*b+1 is divisible by a+b and a+b has g as a factor, therefore g is a factor of a*b+1.  However g is coprime to a*b+1.  Then g must equal 1, which immediately implies a and b are coprime.

Let h be the greatest common divisor of a+b and a-b.  h must then also be a factor of the sum and difference of a+b and a-b.  (a+b)+(a-b) = 2a and (a+b)-(a-b) = 2b.  Then h is a common factor of 2a and 2b.

With a and b being coprime, the only possible values of h are the factors of 2, namely 1 and 2.  Therefore the greatest common divisor of a+b and a-b is either 1 or 2.  QED Lemma 2.

With both lemmas proven we can now state 2*(b^2-1) is divisible by the product (a+b)*(a-b).

Any positive integer is greater than or equal to any of its factors.  Then 2*(b^2-1) >= (a*b)*(a-b).  Rearrange this inequality into 3*b^2 - 2 >= a^2.  Adding 2 to the left side will make the inequality strict: 3b^2 > a^2.

From statement i, a and b are both positive. This means we can take the square root of each side without disturbing the inequality.  Doing so yields sqrt(3)*b > a.  QED

 Posted by Brian Smith on 2016-11-19 12:18:00

 Search: Search body:
Forums (0)