From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math,sci.math.num-analysis Subject: Re: Solving cx^2 + dy = 0 (x,y integers) Date: 5 Mar 1998 05:38:18 GMT In article <34FD45B3.27EEB7F2@hotmail.com>, Dario Alejandro Alpern wrote: >When I entered the equation 12 x^2 + 125 y = 0, it gave the following >answer: ... >x = 25 t (1) >y = -60 t^2 ... >I found a method to get the coefficients in (1) but it involves >factoring the coefficients c and d. Is there any method that does not >need factoring (so the Javascript program, that is interpreted by the >Navigator, runs faster)? To find all solutions to cx^2 = -dy , you can certainly begin by dividing by gcd(c,d) (which can be computed without factoring c and d); then we may assume gcd(c,d)=1, so that c | y and, writing y = -cz, we are left with the equation x^2 = d z . This is easily solved _if_ we can readily write d = e^2 f where f is square-free, namely the solution is x = e f t, z = f t^2 where t is arbitrary. Unfortunately, it is not known how to find the square-free part f of an integer d except by factoring d completely. Indeed, I am not aware of any way to determine whether or not d is squarefree in the first place, except by factorization. dave [That reminder again: "num-analysis" is not number theory! Try sci.math ] ============================================================================== From: nmm1@cus.cam.ac.uk (Nick Maclaren) Subject: Re: Solving cx^2 + dy = 0 (x,y integers) To: rusin@vesuvius.math.niu.edu (Dave Rusin) Date: Thu, 5 Mar 1998 14:46:36 +0000 X-Newsgroups: sci.math,sci.math.num-analysis In article <6dldoa$q1f$1@gannett.math.niu.edu>, you write: |> |> Unfortunately, it is not known how to find the square-free part f of |> an integer d except by factoring d completely. Indeed, I am not aware |> of any way to determine whether or not d is squarefree in the first place, |> except by factorization. There are certainly test methods that do not involve factorisation but, like simple primality tests, they prove only one way and then only for some numbers. I can't remember enough of them offhand to know if any are more efficient than factorisation - for example, I can think of one that isn't! Nick Maclaren, University of Cambridge Computer Laboratory, New Museums Site, Pembroke Street, Cambridge CB2 3QG, England. Email: nmm1@cam.ac.uk Tel.: +44 1223 334761 Fax: +44 1223 334679 ============================================================================== Date: Thu, 5 Mar 1998 09:02:13 -0600 (CST) From: Dave Rusin To: nmm1@cus.cam.ac.uk Subject: Re: Solving cx^2 + dy = 0 (x,y integers) Well, right, I can think of a number of tests which state "If ... then N is not squarefree", but none which state "If ... then N is squarefree", except for conditions "..." which require factorization of N, or proof of the nonexistence of something or other. Example: if there is an a <> 1 mod N with a^N=1 mod N then N is not squarefree. But statistically speaking your chances of finding such an a by random selection in Z/N are poor unless N has only few, small prime divisors. Or were you thinking of something more useful? It's frustrating because the rings Z and F[X] (F any field) are arithmetically similar, and there _is_ an efficient way to find the squarefree parts of elements of F[X]. dave ============================================================================== To: Dave Rusin Subject: Re: Solving cx^2 + dy = 0 (x,y integers) Date: Thu, 05 Mar 1998 16:58:40 +0000 From: Nick Maclaren > But statistically speaking your chances of finding such an a by random > selection in Z/N are poor unless N has only few, small prime divisors. > > Or were you thinking of something more useful? There MAY be a more useful test, but I don't know of one. The inefficient test that I was thinking of involves finding the period of the multiplicative congruential pseudorandom number generator modulo N - that tells you quite a lot about the factorisation of N. But I assert that factorisation is much cheaper, even done cluelessly :-) Regards, Nick.