wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> A Bivariate Divisibility Puzzle
        
(Message started by: K Sengupta on May 30^th, 2006, 8:22pm)

Title: A Bivariate Divisibility Puzzle
Post by K Sengupta on May 30^th, 2006, 8:22pm

Determine all possible pairs (x,y) of positive integers in order that (x^2)/( 8*x*y^2 – 8*y^3 +1) is a positive integer.

Title: Re: A Bivariate Divisibility Puzzle
Post by K Sengupta on Jun 3^rd, 2006, 8:18am

Let us substitute h = x^2/(8*x*y^2 – 8*y^3 +1). Then we have a quadratic equation for m, namely x^2 – 8*h*y^2*x + (8*y^3 - 1)h = 0. This has solutions 4h*y^2 +/- N, where N is the positive square root of 16*h^2*y^4 - 8* h*y^3 + h.

Since y >= 1, h >= 1, N is certainly real. But the sum and product of the roots are both positive, so both roots must be positive. The sum is an integer, so if one root is a positive integer, then so is the other.

The larger root 4h*y^2 + N is greater than 4h*y^2, so the smaller root < h(8*y^3 - 1)/(4*h*y^2) < 2y.So, we can't have y < x < 2y, for otherwise: 8(x-y)y^2 + 1 > (2y)^2 > x^2.
So x < 2y implies x< =y.

So for the smaller root we cannot have x-y > 0. But x-y must be non-negative (since h is positive), so x-y = 0 for the smaller root. Hence 4*h*y^2 - N = y.

Now N^2 = (4*h*y^2 - y)^2 = 16*h^2*y^4 -8* h*y^3 + h, so h = y^2. Substituting y = k we obtain the solutions: (x,y) = (k, k) and (8*k^4 - k, k).

We have shown that any solution must be of one of the two forms given, but it is trivial to check that they are all indeed solutions.

Title: Re: A Bivariate Divisibility Puzzle
Post by Eigenray on Jun 3^rd, 2006, 11:10pm

Interesting. Ignoring the "positive" part, the solutions (x,y) are in bijection with divisors d | (8y³-1)² that are 1 mod 8y², via d = 8y²(x-y)+1.

Since
(8y²x - 8y³ + 1)(8y²x + 8y³ - 1) = (8y²x)² - (8y³-1)²,
and d | x², we have d | (8y³-1)², and clearly d = 1 mod 8y².

Conversely, if d | (8y³-1)², then d | (8y²x)²; since d is relatively prime to 2y, we have d | x², and if also d = 1 mod 8y², we can solve for x = y + (d-1)/(8y²).

The three "trivial" solutions are d = 1, (1-8y³), and (8y³-1)², we correspond to x = y, 0, and y(8y³-1), respectively. Are there any others? That is, if z is even, and d | (z³-1)², and d = 1 mod 2z², must d be either 1, (1-z³), or (z³-1)²? Equivalently, when allowing x,y to be arbitrary integers, are any new solutions added except x=0 or y=0?

on 06/03/06 at 08:18:36, K Sengupta wrote:

But note that if x-y > 0, then since h > 0, we must have the denominator 8*(x-y)*(y^2 )+ 1 smaller than the numerator and hence x>y.

I don't understand "hence x>y" here. Perhaps a better phrasing is: we can't have y < x < 2y, for otherwise
8(x-y)y² + 1 > (2y)² > x².
So x < 2y implies x<y.

Title: Re: A Bivariate Divisibility Puzzle
Post by K Sengupta on Jun 8^th, 2006, 7:58am

On Jun 3rd, 2006, 11:10pm, Eigenray wrote:

Quote:

I don't understand "hence x>y" here.

Incorporated the necessary amendments in my previous post in conformity with the abovementioned suggestion.
Also, corrected some typographical anomalies is the said post. Consequently, the said post is now fit for public display.
Thanks, Eigenray.

On Jun 3rd, 2006, 11:10pm, Eigenray wrote:

Quote:

Are there any others? That is, if z is even, and d | (z³-1)², and d = 1 mod 2z², must d be either 1, (1-z³), or (z³-1)²? Equivalently, when allowing x,y to be arbitrary integers, are any new solutions added except x=0 or y=0?

Despite my best efforts I have not been able to determine any further solutions, and accordingly, I am still looking for them.