[seqfan] Re: Determine whether a number is represented by a binary quadratic form

[Georgi Guninski]

On Sat, Jul 10, 2010 at 05:08:38PM -0700, T. D. Noe wrote:
> The are many sequences generated by binary quadratic forms.  Suppose we
> have a quadratic form
> 
> 	f(x,y) = ax^2 + bxy + cy^2
> 
> with integers a, b, and c.  For integer N, we want to know whether N =
> f(x,y) has a solution for x and y relatively prime.  It appears that we can
> look at the reduced equation
> 
> 	az^2 + bz + c = 0 (mod N)
> 
> If it has an integer solution z=z0, then there is a solution to N = f(x,y).
> In fact, the number of solutions to the reduced equation is the same as the
> original equation
> 
> Is there a name for this process?  Can the solution (x,y) be determined
> from z0?
>


looks like if b = 0 the equation must have solutions mod a and mod c, e.g.:

2 x^2+2^3 y^2=13 [1]

mod 13 == n:
2x^2+2^3y^2 = 0 <=> z^2+2^2 = 0, z = x/y = 3 is a solution

the LHS of [1] is even and RHS is odd.