Proof of Binary Quadratic Forms and Modulo Squares with Hint

[b0mb0nika]

show that if a number n is represented by a quadratic form f of discriminant d then 4an is a square mod |d|.

I have no clue how to even start this proof. I tried using the jacobi symbol.. but it's not gettin me anywhere.

Could someone give me a hint..

 

[Hurkyl]

show that if a number n is represented by a quadratic form f of discriminant d

I can't translate this into something that makes sense. But I might just not be familiar with the jargon. What does it mean for this to be so?

 

[shmoe]

$$f(x,y)=ax^2+bxy+cy^2$$ is a binary quadratic form with discriminant $$d=b^2-4ac$$. (a, b, c integers).

Saying n is represented by f means we have integers x, y where $$n=f(x,y)$$.

So we just have to show $$4af(x,y)=4a^2x^2+4abxy+4acy^2$$ is a square mod |d|.

But this b0mb0nika knows

hint:replace $$4ac$$ with $$b^2-d$$, expand and stare.

 

[Hurkyl]

Or... just complete the square!


I figured it was something like that -- I just didn't get from "represented by a quadratic form" to "an evaluation of a quadratic form".

Interestingly enough, I've recently used almost this exact thing -- it's the key bit of theory behind the multiple polynomial quadratic sieve! (slightly different, but morally the same!)

 

[b0mb0nika]

ok well if u put it that way it's not that hard:)
ok related to that question i have to show that if p = x^2+5y^2
than (p/5 ) ( the legendre symbol) = 1 or 0 and that p is represented like that iff
p =5 or p == 1 or 9 mod (20)

ok this is what i did:
discriminant = -20

i showed that (p/5) = 1 or 0

now if p = 5 or 1 or 9 ( mod 20)
let p = ax^2 + bxy + cy^2
then 4ap == 1,4,9,16 ( mod 20)
then ap == 1,4,9 or 16 (mod 20) or ap=5
so now i just show that it works for a=1 and p =5 or p == 1,9 ( mod 20)

and the other way
p = x^2 + 5p^2
then 4p==0,1,4,9,16 ( mod 20)
but we can write p= x^2+5y^2 only for p= 5 or p == 1 or 9 ( mod 20 )

ok does it make sense ?

 

[Hurkyl]

now if p = 5 or 1 or 9 ( mod 20)
let p = ax^2 + bxy + xy^2

I assume you meant cy^2. This raises a flag, though: the identity of p has already been specified, so you can't use this "let" statement to define p. Presumably you mean it to specify a, b, c, x, and y, but that begs the question "Why can p be written in that form?"


As for the other direction, I don't follow at all. You're correct that 4p is equivalent to 0, 1, 4, 9, or 16, but the next sentence doesn't make any sense.

 

[b0mb0nika]

yes i did mean cy^2

for the frist part i guess i just assumed that p could be written as a binary quadratic form... i'll have to think about that

and for the second part i just took 4p = 0 ( mod 20), 4p = 1 ( mod 20 ) .. etc.. and solved for p

 

[b0mb0nika]

ok let me see if i got the first part now :

let p = 5 or 1 or 9 ( mod 20)
then p can be written as follows p = ax^2 + bxy + cy^2 ( for all p : you can let
a=p and x =1, y = 0 )

then 4ap == 1,4,9,16 ( mod 20)
then ap == 1,4,9 or 16 (mod 20) or ap=5
but we already said p =5 or p == 1 or 9 ( more 20 )
then a = 1
because the discriminant is not a perfect square ( 20 ) -|a|<b<=|a|<|c|
so b could be 0 or 1
b = 1 is impossible ( 1-4ac = |20| => c is not an integer )
so b = 0 , in which case - 4ac = -4c = -20 so c = 5

 

[Hurkyl]

Justify your steps.

P.S. you do realize that if 4x=y (mod 20) has one solution for x, then it has 4 solutions, right?

 

[b0mb0nika]

i'm not exactely sure what u mean.. but i think i got it more or less right..i'm going to write it like that.. maybe explain more what i did..
thx again for the hint

 

[Hurkyl]

Then you might want to look at it again -- I don't follow a single step of your argument.

 

[shmoe]

ok let me see if i got the first part now :

let p = 5 or 1 or 9 ( mod 20)
then p can be written as follows p = ax^2 + bxy + cy^2 ( for all p : you can let
a=p and x =1, y = 0 )

then 4ap == 1,4,9,16 ( mod 20)
then ap == 1,4,9 or 16 (mod 20) or ap=5
but we already said p =5 or p == 1 or 9 ( more 20 )
then a = 1
because the discriminant is not a perfect square ( 20 ) -|a|<b<=|a|<|c|
so b could be 0 or 1
b = 1 is impossible ( 1-4ac = |20| => c is not an integer )
so b = 0 , in which case - 4ac = -4c = -20 so c = 5

It looks like you're skipping something here. You need to first show that p can be represented by a quadratic form with discriminant -20. Then you can can take an equivalent reduced form and use those bounds on the coefficients. I'm not clear on how you're limiting what 4ap is though?

At this point you could also use your bounds on the coefficients and b^2-4ac=-20 to show that a=1 or 2. This, and consideration of the discriminant again, reduces the number of forms you have to consider to 2 (or 3 if you don't have the machinery to force b>=0), and you can rule out the other by considering it modulo something convenient. This has the added bonus of finding (with a small amount of extra work) a quadratic form that represents primes congruent to 3 and 7 mod 20.