Re: Quadratic equation

sttscitrans@xxxxxxxxx wrote:
bert wrote:
Edwin Klement wrote:
can somebody give me a hint how to solve an quadratic equation like 3*x*x
+ y*y - n = 0
where x, y and n are positive integer.

I can't see any problem. Remove any square factors
of N,

You could miss some solutions

Yes, I was careless, I forgot that the square factors
removed here might have their own solution of the
congruence W^2 = -3 (mod F^2), in which case they
should be left in, and their solution combined with
the others by the Chinese Remainder Theorem.

then solve W^2 = -3 (mod N). If N is a prime
of the form 6n+1, there is only 1 solution. If it is a
product of m such primes, there are 2^m solutions,
combined by the Chinese Remainder Theorem
from the solutions for each factor. Finally, expand
N/W as a continued fraction. The convergents
provide x^2 + 3y^2 = k.N for steadily decreasing
then increasing k. k=1 always seems to occur
in the middle, but I can't prove it.

Example: N = 28825 = 5^2 . 1153.

148^2 = -3 mod 1153.
148^2 + 3 = 19 . 1153
117^2 + 3 . 7^2 = 12 . 1153
31^2 + 3 . 8^2 = 1153

155^2 + 3 . 40^2 = 28825

I get the convergents of 1153/148 to be 7/1, 8/1,
31/4, 39/5, 148/19, 335/43, 818/105, 1153/148 . . .

Yes, sorry, I was being a bit loose with the
terminology. The continued fraction expansion
tells us first that 7 * 148 = -117 (mod N), from
which we can construct the next congruence
117^2 + 3 . 7^2 = 0 (mod N). Similarly from
8 * 148 = 31 mod N, we can construct the
third one 31^2 + 8 . 3^2 = 0 mod N.

There are several different ways of combining
and reducing the congruences provided by the
continued fraction expansion, as shown in your
example. It's a matter of taste and preference.
--

.

Relevant Pages

  • Re: Simple number theory problem...
    ... Obviously n and n+1 have no prime factors in common. ... or is a square, and the other is p times a square. ... the continued fraction expansion of sqrt. ...
    (sci.math)
  • Re: Im not the only one who values interval-arithmetic
    ... > I believe Bill Gosper did basically the same thing circa 1975 using ... The primitive functions pipeline the computation ... is the number to find the square root of. ... where X is the continued fraction, ...
    (comp.lang.lisp)
  • Re: Quadratic equation
    ... Yes, I was careless, I forgot that the square factors ... product of m such primes, there are 2^m solutions, ... N/W as a continued fraction. ... I get the convergents of 1153/148 to be 7/1, 8/1, ...
    (sci.math)
  • Re: square root continued fraction
    ... period, now i start generating approximation to p/q, it certainly ... terms of continued fraction for sqrt. ... Square roots are a bit special, ... may have some pretty big partial quotients. ...
    (sci.math)
  • Re: Surrogate factoring, objective look
    ... > I have found a factorization method which I claim is new and important. ... and comparing it with congruence of squares. ... > quadratics. ... > and if that square root is an integer, then you have an integer x. ...
    (sci.crypt)