wu :: forums - Print Page


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

        riddles >> easy >> Divide two expressions, get perfect square?
        
(Message started by: K Sengupta on Jul 27^th, 2007, 8:06am)

Title: Divide two expressions, get perfect square?
Post by K Sengupta on Jul 27^th, 2007, 8:06am

Analytically determine whether there exists any pair of positive integers (x, y) satisfying:
(x²⁰⁰⁰ – 1)/(x-1) = y²

Title: Re: Divide two expressions, get perfect square?
Post by Eigenray on Jul 31^st, 2007, 10:58am

I must be missing the "easy" solution! First observe:

[hideb]x²⁰⁰⁰-1 = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/prod.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/phi.gif_n(x),
where the product is over divisors n of 2000, and http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/phi.gif_n is the n-th cyclotomic polynomial.

Now, for n http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif m, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/phi.gif_n and http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/phi.gif_m are relatively prime, since they are both irreducible, and therefore 1 is a linear combination of http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/phi.gif_n and http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/phi.gif_m, with coefficients in http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbq.gif[x]. Clearing denominators, we get a relation of the form d = f http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/phi.gif_n + g http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/phi.gif_m, where d is an integer, and f,g http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gif[x]. Then for any integer x, gcd(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/phi.gif_n(x), http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/phi.gif_m(x)) must divide d. For any given n,m, this value d can be found using the Euclidean algorithm, and it turns out that for n,m divisors of 2000, d is either 1,2, or 5.[/hideb]
Here's a [link=http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_putnam;action=display;num=1185906352]question[/link] (but this goes beyond easy, I'm sure): find a closed form for d, in terms of n and m.

Anyway, given the above, lets find all integer solutions:[hideb]
Since any two factors http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/phi.gif_n(x) and http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/phi.gif_m(x) have a gcd of 1,2, or 5, and the product is a square, it follows that each factor is of the form 2^a5^b*y², where a,b are either 0 or 1. [Note that for n>2, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/phi.gif_n(x)>0 for all x, since it has no real root.]

Since http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/phi.gif₈(x) = x⁴+1 is never divisible by 5, it is either a square, or twice a square. But if x⁴+1=y², then 1=y²-x⁴ is the difference of two squares, which happens only for y²=1, x=0. Aside from this solution, we can conclude therefore that x⁴+1 is twice a square, and therefore x is odd.

Now observe that http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/phi.gif₅(x) = 1+x+x²+x³+x⁴, and http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/phi.gif₁₀(x) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/phi.gif₅(-x) are always odd. Moreover, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/phi.gif₅(x) is divisible by 5 iff x=1 mod 5, and 5 | http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/phi.gif₁₀(x) iff x=-1 mod 5. WLOG, then (replacing x with -x if necessary), http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/phi.gif₅(x) is not divisible by 5.

It follows now that http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/phi.gif₅(x) must be a square. But! x is odd, and
(x²+(x-1)/2)² < x⁴+x³+x²+x+1 < (x²+(x+1)/2)²,
since the difference on the left is 7x²/4+3x/2+3/4 > 0, and the difference on the right is x²/4 - x/2 - 3/4 > 0 when x < -1, or x > 3. This leaves only x=-1,1,3 to consider, which is straightforward.[/hideb]

Thus the only integer solutions are (0,http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pm.gif1), and (-1, 0). Phew!

Title: Re: Divide two expressions, get perfect square?
Post by towr on Jul 31^st, 2007, 12:16pm

Can't we do something with (x²⁰⁰⁰ – 1)/(x-1) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif¹⁹⁹⁹_i=0 xⁱ?

[e] If I'm not mistaken xⁱ mod m is periodic with period m or some smaller factor of it. So among other things (x²⁰⁰⁰ – 1)/(x-1) should be 0 modulo every m that divides 2000. Right? But is that remotely useful... hmm[/e]

Title: Re: Divide two expressions, get perfect square?
Post by Eigenray on Jul 31^st, 2007, 3:40pm

I'm not sure what.

If 2000 were odd, say f(x) is a monic polynomial of even degree 2n, we could expand http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.giff(x) = g(x) + O(1/x), where g is a polynomial with rational coefficients of degree n. If f is not a perfect square, then f(x) - g(x)² = c*x^k + O(x^k-1), with c http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif 0, and k < n.

For each congruence class of x mod the LCM of the denominators of g's coefficients, find a rational t, 0 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif t http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif 1, such that g(x)-t is integer (don't take t=1 if c>0, nor t=0 if c<0). Then

(g(x)-t)² < f(x) < (g(x)+1-t)²

for x sufficiently large. More generally, I guess if f(x) is monic of degree kn, and is not a perfect k-th power, then f(x)=y^k has only finitely many solutions, which can be found constructively? (Sounds right but if so I'm surprised I didn't know that.)

I didn't get anywhere considering (x²⁰⁰⁰-1)/(x-1) mod m for various m.

Title: Re: Divide two expressions, get perfect square?
Post by K Sengupta on Aug 6^th, 2007, 8:05am

A proposed solution is furnished hereunder as follows:

[hide]Substituting (a, b, c) = {x^1000 + 1, x^500 + 1, (x^500 – 1)/(x-1)}

we obtain:

(x^2000 – 1)/(x-1) = abc

Now b and c divide a-2, while c divides b-2.

Accordingly, it follows that the gcd of any two of a, b and c is at most 2.

The product abc is a perfect square if a, b and c are either squares or doubles of squares.
It is clearly observed that neither a nor b can be squares of positive integers.

Accordingly, each of a and b must correspond to twice the square of positive integers.

Therefore, we must have:

4ab = 4*x^1500 + 4*x^1000 + 4*x^500 + 4 must be a perfect square.

However, in that situation:
(2*x^750 + x^250)^2 < 4*x^1500 + 4*x^1000 + 4*x^500 + 4
< (2*x^750 + x^250 + 1)^2

This implies that 4ab is not a perfect square, which leads to a contradiction.

Consequently, the given equation does not admit of positive integer solutions.[/hide]

Of course, the non negative integer solutions are indeed : (0, +/-1), and (-1, 0) as rightly pointed out by Eigenray.

In conclusion, I personally consider the above solution in terms of the current post to be much inferior in quality when compared to Eigenray's superior methodology.

Title: Re: Divide two expressions, get perfect square?
Post by Eigenray on Aug 7^th, 2007, 6:21am

on 08/06/07 at 08:05:03, K Sengupta wrote:

In conclusion, I personally consider the above solution in terms of the current post to be much inferior in quality when compared to Eigenray's superior methodology.

??? I don't know why you would say that. Yours is more elementary and only requires that 2000 = 8n. Mine only works for 2000 = 40n, where n is a product of powers of 2 and 5.