| >>> Consider the following diophantine equation in x and y:
>>> x^2 + (x+1)^2 + ... + (x+n-1)^2 = y^2, (*)
>>>
>>> If (*) has no solutions, we say that n is bad.
>>> (i) Prove that 3, 4, 5, 6, 7, 8, 9 and 10 are bad.
does "diophantine" have a restriction on the values for x and y?
(I'm dutch so some english words or mathematical terms are unknown to me)
if not, take n = 4, x = -1/2 and y = 3
x = -5/2 and y = 3
and (*) holds
Marjan
|
| ok, here goes:
Rather than clutter up this reply with the full proof I'll use a theorem
(SOP Son of Pell) which I like to think of as my own but is probably
standard textbook stuff (break it to me gently :-).
From memory it goes as follows, although as I type I'm not sure I remember it
exactly right. The mc� seems relatively right :-) but I may have misremembered
the magic constant. I'll reconstruct the proof and maybe append it as a reply.
The equation X� - nY� = m can be solved as follows:
- if n = k� then it has zero or a finite number of solutions (got by
the different associations of factors (X - kY)(X + kY) with factors
of the rhs.
- if n /= k� then it has zero or an infinite number of solutions
derived as follows:
Find all solutions with Y <= sqrt(mc�) and then generate the
remainder by applying to them the transformation
(a nc)(X) (T)
(c a )(Y)
where (a,c) is the smallest solution to the (Pell) equation
a� - nc� = 1
(always soluble using the Pell continued fraction trick)
If we can't find any solutions with Y <= mc� then there are
no solutions at all.
Back to the real questions:
(a)The equation reduces to the following:
X� - nY� = (n-1)n(n+1)/3 (I)
where X = 2y
and Y = 2x + n - 1
so we need to find solutions to (I) with X even and
Y having opposite parity to n for n to be good. (II)
If Y > n - 1 then n is very good.
To prove that 2, 11, 24 and 26 are infinitely good we have only to
find one solution satisfying (II) and then the rest follows from SOP,
since the transformations (T) preserve the properties (II).
(i) X� - 2Y� = 2 has the solution (X,Y) = (2,1)
(ii) X� - 11Y� = 10*11*12/3 must have X = 11Z, so
11Z� - Y� = 40
which has the solution Z = Y = 2 so (X,Y) = (22,2)
(out of interest the generators for an infinite set are,
in the terminology of SOP (a,c)= (10,3))
(iii)X� - 26Y� = 25*26*27/3 can be re-arranged as
X� - 26Y� = 3�*26*(26 - 1)
= (3*26)� - 26*3�
so a solution is (78,3) (and a solution to (b) is looming large)
(iv) X� - 24Y� = 23*24*25/3 must have X = 2Z
Z� - 6Y� = 1150
which has the solution Z = 38, Y = 7 (had to work to get
that one) so (X,Y) = (76,7)
(b)Is easy from (a)(iii).
If n = 3q� - 1 then the identity
(3(3q� - 1))� - (3q� - 1)3� = (3q� - 2)(3q� - 1)(3q�)/3
shows that (3(3q� - 1),3) is a solution for all q.
((a) has the examples q = 1,2,3)
(c)Follows from SOP since we can transform enough times to make Y > n - 1
(d)From what we have so far, the case n being very good, but not
infinitely good, can only arise if n = k�.
If n is even = 4k� then we need to examine separately the cases
k = 3j + 1, 3j and 3j - 1. I won't do the third, it is very similar to
the first.
(i) If n = (2*3j)� then
X� - 36j�Y� = (36j� - 1)36j�(36j� + 1) which must have X = 6jZ
3Z� - 3Y� = (36j� - 1)(36j� + 1)
which is impossible since the rhs is not divisible by 3
(ii) If n = (2(3j + 1))� then, since we must have X = 2(3j + 1)Z we
can say that
Z� - Y� = an expression of the form 4i + 1 (boring steps omitted)
Now all factorisations of 4i + 1 must be of the form
(4e + 1)(4f + 1) or (4e - 1)(4f - 1)
and matching any of them to (Z + Y)(Z - Y) means that Y = 2(e-f),
which is even, violating (II)
So n cannot be even.
(e)49 is a square so can't be infinitely good.
X� - 49Y� = 48*49*50/3 must have X = 7Z
Z� - Y� = 800
Examining the various factorisations a*b of 800 and trying
Z = (a + b)/2 and Y = (a - b)/2, and making a and b differ as much
as possible to try and make Y > n - 1 (for very goodness) we find
a = 200, b = 4, Z = 102, Y = 98 (> n-1)
and again we can anticipate a general method, this time for (f),(h)
so (X,Y) = (714,98) which is very good.
(f)We just need to show that there are an infinite number of squares that are
very good. We have proved in (d) that n cannot be even. Also a slight
variant on (d)(i) shows that n can't be divisible by 3.
So, let's look at the remaining cases, n = (6k - 1)� and n = (6k + 1)�
If n = (6k - 1)� we must have X = (6k - 1)Z and
Z� - Y� = 8k(3k - 1)(18k� - 6k + 1)
in the spirit of (e) we take the "best" factorisation which is
Z + Y = 2k(3k - 1)(18k� - 6k + 1)
Z - Y = 4
so Z (and X) is even and Y = k(3k - 1)(18k� - 6k + 1) - 2
Very goodness requires Y > n - 1
ie k(3k - 1)(18k� - 6k + 1) - 2 > 12k(3k - 1)
ie k(3k - 1)(18k� - 6k - 11) - 2 > 0
which is true for k > 1 (but not k = 1, ie n = 25)
If n = (6k + 1)� the algebra is very similar, but things are very good
for all positive k.
(g)If n = 25 then setting X = 5Z we have
Z� - Y� = 208 and the best factorisation we can manage is
Z = 28 (so X = 140), Y = 24 which is good but not very good
since Y is not > n - 1
(h)We did more than we needed in (f) and this is proved.
(i)Since 4k� and 9k� are bad (f) this takes care of 3,4 and 9
The rest can be proved using SOP.
There is a quick proof for n = 5 though:
X� - 5Y� = 40 must have X = 5Z
5Z� - Y� = 8
but this means Y� ends in 2 or 7 which is impossible.
There is a similar quick proof for n = 10
(j)We've done. 4k� is always bad.
(k)If n is a square then (f) gives a good algorithm, namely
If n = (6k + 1)� (k>0) or (6k + 1)� (k>1) then n is very good
If n = 25 then n is good
Otherwise n is bad
If n is not a square then SOP gives a reasonable algorithm, but can be
tactically improved as shown by some of the working here.
Dick
|
| Here is a proof of SOP as promised.
Theorem: SOP
The equation:
X� - nY� = m (Integral n > 0, integral m) (II)
has integral solutions as follows:
If n = k� then it has a finite, possibly zero, number of solutions.
If n /= k� then it has no solutions, or an infinite number derived as
follows:
Find all solutions with (X,Y) with Y <= sqrt(mc�) (if m>0)
or Y <= sqrt(mc� + 1/n) (if m<0)
where (a,c) is the smallest solution to the equation:
a� - nc� = 1 (excluding the trivial solution (1,0))
Then a complete set of solutions is given by:
(a nc)(X)
(c a )(Y)
Proof:
The equation can be analysed as follows:
(1) If n = k� then (II) factorises:
(X + kY)(X - kY) = m
which yields a finite, possibly zero, number of solutions by
associating factorisations of the rhs with the lhs.
(2) If n /= k� then, if we can find a solution (X) then
(Y)
(a nc)(X) and (a -nc)(X) (III,IV)
(c a )(Y) (-c a )(Y)
will also be solutions, provided a� - nc� = 1 (V)
( (IV) is the inverse of (III) ).
Now (V) is our old friend Pell's equation which can always be solved using
the continued fraction trick.
If we can solve (II) then a smaller solution exists (using IV) if
X > aX - ncY (i)
aX - ncY > 0 (ii)
Y > -cX + aY (iii)
-cX + aY > 0 (iv)
(i) is true if ncY > (a - 1)X
ie if n�c�Y� > (a - 1)�X�
= (a - 1)�(nY� + m) (using II)
ie if Y�(n�c� - a�n + 2an - n) > (a - 1)�m
ie if Y�(2an - 2n) > (a - 1)�m (using V)
ie if Y� > (a - 1)/2n
ie if Y� > mc�/2(a+1)
(ii) is true if a�X� > n�c�Y�
ie if a�(nY� + m) > n�c�Y� (using II)
ie if Y�(a�n - n�c�) + ma� > 0
ie if Y�n > -ma� (using V)
ie if Y� > -ma�/n
ie if Y� > -m(c� + 1/n) (using V again)
(iii) is true if cX > (a - 1)Y
ie if c�X� > (a - 1)�Y�
ie if c�(nY� + m) > (a - 1)�Y� (using II)
ie if Y�(nc� - a� + 2a -1) > -mc�
ie if Y� > -mc�/2(a-1) (using V)
(iv) is true if aY > cX
ie if a�Y� > c�X�
= c�(nY� + m) (using II)
ie if Y�(a� - nc�) > mc� (using V)
ie if Y� > mc�
If m > 0 then only (i) and (iv) are relevant and (iv) is the stronger.
If m < 0 then only (ii) and (iii) are relevant and (ii) is the stronger.
Let K = mc� (m>0) or m(c� + 1/n) (m<0). Then any solution to (II) with Y� > K
can be mapped, by a number of applications of (IV), into a solution with
smaller Y. Therefore, having found all the solutions with Y� <= K, we can
apply the mapping (III) any number of times to each to obtain all solutions.
Dick
|