- #1

- 37

- 0

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..

- Thread starter b0mb0nika
- Start date

- #1

- 37

- 0

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..

- #2

Hurkyl

Staff Emeritus

Science Advisor

Gold Member

- 14,916

- 19

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?show that if a number n is represented by a quadratic form f of discriminant d

- #3

shmoe

Science Advisor

Homework Helper

- 1,992

- 1

Saying n is represented by f means we have integers x, y where [tex]n=f(x,y)[/tex].

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

But this b0mb0nika knows

hint:replace [tex]4ac[/tex] with [tex]b^2-d[/tex], expand and stare.

- #4

Hurkyl

Staff Emeritus

Science Advisor

Gold Member

- 14,916

- 19

I figured it was something

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!)

- #5

- 37

- 0

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 jsut 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 ?

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 jsut 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 ?

Last edited:

- #6

Hurkyl

Staff Emeritus

Science Advisor

Gold Member

- 14,916

- 19

I assume you meantnow if p = 5 or 1 or 9 ( mod 20)

let p = ax^2 + bxy + xy^2

As for the other direction, I don't follow at all. You're correct that

- #7

- 37

- 0

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

- #8

- 37

- 0

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

- #9

Hurkyl

Staff Emeritus

Science Advisor

Gold Member

- 14,916

- 19

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

- #10

- 37

- 0

thx again for the hint

- #11

Hurkyl

Staff Emeritus

Science Advisor

Gold Member

- 14,916

- 19

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

- #12

shmoe

Science Advisor

Homework Helper

- 1,992

- 1

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?b0mb0nika said:

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

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.

- Last Post

- Replies
- 7

- Views
- 4K

- Last Post

- Replies
- 2

- Views
- 2K

- Last Post

- Replies
- 1

- Views
- 2K

- Last Post

- Replies
- 5

- Views
- 5K

- Last Post

- Replies
- 3

- Views
- 2K

- Last Post

- Replies
- 3

- Views
- 3K

- Last Post

- Replies
- 2

- Views
- 2K

- Last Post

- Replies
- 1

- Views
- 3K

- Replies
- 3

- Views
- 5K

- Last Post

- Replies
- 4

- Views
- 2K