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

        riddles >> medium >> Integer Constant And Divisibility
        
(Message started by: K Sengupta on Jun 5th, 2008, 7:34am)
Title: Integer Constant And Divisibility
Post by K Sengupta on Jun 5th, 2008, 7:34am
C is a positive integer such that both (C*m + 1) and  C*(m+1) + 1 are perfect squares, where m is a positive integer constant.

Prove that C is always divisible by 8(2m+1).
Title: Re: Integer Constant And Divisibility
Post by Eigenray on Jun 5th, 2008, 9:53am
Some thoughts:

write mC+1 = r2,  (m+1)C+1 = s2,  h=s-r.  Then

(r - mh)2 = m(m+1)h2 + 1.

If (m, h, r, C) is a solution, with C = h(2r+h)) and r2 = mC+1, then (m, h', r', C') is a solution, where h' = h+2r, r' = r+2mh', C' = h'(h'+2r').  So there is an infinite family of parameterizations:

h0(m) = 0;  r0(m) = 1;  C0(m) = 0.
h1(m) = 2;  r1(m) = 4m+1;  C1(m) = 16m + 8.
h2(m) = 4(2m+1);  r2(m) = 16m2+12m+1;  C2(m) = (8m+4)(32m2 + 32m + 6)
h3(m) = 2(4m+1)(4m+3);  r3(m) = 64m3 + 80m2 + 24m + 1;
h4(m) = 8(2m+1)(8m2+8m+1);  r4(m) = (4m+1)(64m3 + 96m2+36m+1)
...
hn = hn-1 + 2rn-1;  rn = rn-1 + 2mhn;  Cn = hnhn+1.

Since

h'' = h' + 2r'
= h+2r + 2(r+2m(h+2r))
= (4m+1)h + 4(2m+1)r,

and 4(2m+1) | h0, it follows 4(2m+1) | hn for all even n; and since 2|h1, it follows 2|hn for all odd n.  Therefore Cn = hnhn+1 is divisible by 8(2m+1) for all n,m.

So it suffices to show that this family contains all solutions.  A program suggests that this is true.

We may solve the above recurrence to get

hn = [ (1+2m+2x)n - (1+2m-2x)n ]/(2x),
rn = [ (x-m)(1+2m-2x)n + (x+m)(1+2m+2x)n ]/(2x),

where x = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif(m(m+1)).
Title: Re: Integer Constant And Divisibility
Post by Eigenray on Jun 5th, 2008, 10:55am
Oh.  This is actually just [hide]Pell's equation[/hide].  We need only check that [hide](2m+1, 2) is the fundamental solution to x2 - m(m+1)y2 = 1[/hide].


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