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

        riddles >> hard >> Find The Pairs (X, Y)
        
(Message started by: K Sengupta on Aug 2nd, 2007, 8:01am)
Title: Find The Pairs (X, Y)
Post by K Sengupta on Aug 2nd, 2007, 8:01am
Analytically determine all pairs of integers (X, Y) with X>=3 and Y>=3 such that there exists infinitely many positive integers Z for which (ZY + Z2 -1) divides :
(ZX + Z -1)  
Title: Re: Find The Pairs (X, Y)
Post by Eigenray on Jun 21st, 2008, 4:41pm
Well, this was a fun one!

I'll change notation a bit.  Let F(x) = xn+x2-1, G(x) = xm+x-1.

Suppose F(x) | G(x) for infinitely many integers x.  Write G(x) = q(x)F(x) + r(x), where deg r < deg F.  Then r(x)/F(x) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gif 0 as x http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/infty.gif, and is an integer infinitely often.  It follows r http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 0, so F | G as polynomials.

First suppose n is even.  If http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif is a root of F, then -http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif is too, and they must both be roots of G.  But this means http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gifm = 1-http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif, and (-http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif)m = 1+http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif, which is a contradiction because 1-http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif and 1+http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif are neither the same nor negatives of each other.

Now the hard case: n odd.

First: Since F' < 0 only for 0 < x < (2/n)1/(n-2), and F(0)<0, F has a unique real root http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif, with 0 < http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif< 1.  Let h(t)=t-t2.  Since http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gifn+http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif2 = 1, and http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gifn<http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif2, we have
h(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif) < h(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif2) = h(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gifn),
and therefore
http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif2n+http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif-1  <  http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gifn+http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif2-1 = 0 = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gifm+http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif-1.
It follows m < 2n.

Now, let
(1-x)/(1-x2-xn) = 1 - x + x2 + a3x3 + a4x4 + ....
Then ak = ak-2 for 1<k<n, and ak = ak-2 + ak-n for k http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif n.  It's easy to verify that:
ak = (-1)k,  0 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif k < n;
an+2i = i,  0 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif i http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif (n-1)/2;
an+2i+1 = -i, 0 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif i http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif (n-3)/2.

Finally, note that G/F must agree with (1-x)/(1-x2-xn) for the first m-1 terms.  But G/F is a polynomial of degree m-n.  It follows that the n-1 consecutive terms am-n+1,...,am-1 are all 0.  But m<2n, and from a0 to a2n-1 the only zeros are an and an+1.  Therefore m-n+1=n, m-1=n+1, giving n=3, m=5, and we check that indeed G/F = 1-x+x2.

:)


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board