Elliptic Curve y^2 = x^3 +17; show N_p = p

  • Thread starter kingwinner
  • Start date
  • #1
1,270
0

Main Question or Discussion Point

Theorem: Suppose that p is an odd prime and p≡2 (mod 3). Let E be the elliptic curve defined by [tex]y^2 = x^3 + 17[/tex]. Then [tex]N_p[/tex], the number of solutions mod p of the elliptic curve E, is exactly equal to p.
[hint: if p is a prime, then [tex]1^k, 2^k, ..., (p-1)^k[/tex] form a reduced residue system (mod p) if and only if gcd(k, p-1)=1.]

Does anyone have any idea how to prove that [tex]N_p = p[/tex]?
Any help is greatly appreciated! :) (If possible, please explain in simpler terms. In particular, I have no background in abstract algebra.)
 

Answers and Replies

  • #2
336
0
Theorem: Suppose that p is an odd prime and p≡2 (mod 3). Let E be the elliptic curve defined by [tex]y^2 = x^3 + 17[/tex]. Then [tex]N_p[/tex], the number of solutions mod p of the elliptic curve E, is exactly equal to p.
[hint: if p is a prime, then [tex]1^k, 2^k, ..., (p-1)^k[/tex] form a reduced residue system (mod p) if and only if gcd(k, p-1)=1.]
I almost funked at this at the first sight :tongue: . The problem doesn't require any algebraic number theory as I thought.
First, note that p is not 3 . Also, if (x',y') is a solution, so is (x',-y'). Thus, the solutions occur in pairs unless when y'=0 . (I)
If y*^2 = u^3 + 17 = v^3 + 17 with u,v distinct mod p, we must have
u^2+uv+v^2 =0 (mod p). Thus, (2u+v)^2 + 3v^2 = 0 mod p. Since -3 is not a quadratic residue mod p ( remember that p =2 mod 3) , we must have v=0=u.(II)

To follow the hint, gcd(p,3) =1. For k=3, {x^3 +17} (0<=x< p) is a complete residue system (mod p).Hence, it contains exactly (p+1)/2 quadratic residues.This,in view of (I) & (II) gives (p+1)-1 =p solutions.
 
  • #3
1,270
0
I almost funked at this at the first sight :tongue: . The problem doesn't require any algebraic number theory as I thought.
First, note that p is not 3 . Also, if (x',y') is a solution, so is (x',-y'). Thus, the solutions occur in pairs unless when y'=0 . (I)
If y*^2 = u^3 + 17 = v^3 + 17 with u,v distinct mod p, we must have
u^2+uv+v^2 =0 (mod p). Thus, (2u+v)^2 + 3v^2 = 0 mod p. Since -3 is not a quadratic residue mod p ( remember that p =2 mod 3) , we must have v=0=u.(II)

To follow the hint, gcd(p,3) =1. For k=3, {x^3 +17} (0<=x< p) is a complete residue system (mod p).Hence, it contains exactly (p+1)/2 quadratic residues.This,in view of (I) & (II) gives (p+1)-1 =p solutions.
In the last paragraph, do you mean gcd(p,3)=1 or gcd(p-1,3) =1??
Also, The hint says it's a REDUCED residue system mod p, how did you get that {x3 +17: x=0,1,2,...,p-1} a COMPLETE residue system?

Also, why does this prove that Np=p? I don't understand what you're trying to do in (II). Can you explain a little more, please?

Thanks for your help! :)
 
Last edited:
  • #4
336
0
Soryy for the slip - I meant gcd(p-1,3) =1 in the last paragraph.
The hint says that the kth powers of 1,2,...,p-1 form a reduced residue system mod p. Add 0^k =0 to get a complete residue system. Adding a constant (=17)
doesn't change the the complete nature of the system.
Therefore, we get (p+1)/2 distinct quadratic residues out of this (one of them being zero); say congruent to 0, y1^2,... ,yn^2 ( n=(p-1)/2 ) with corresponding values of x equal to x0,x1,.. ,xn.
Listing the solutions ,
(x0,0) , (x1,+-y1), (x2,+-y2)... = 1 + 2n =p.
 
  • #5
1,270
0
Assuming that [tex]1^3, 2^3, ..., (p-1)^3[/tex] form a reduced residue system mod p, does this always imply that [tex]0^3, 1^3, 2^3, ..., (p-1)^3[/tex] will form a complete residue system mod p? Why?


If y*^2 = u^3 + 17 = v^3 + 17 with u,v distinct mod p, we must have
u^2+uv+v^2 =0 (mod p). Thus, (2u+v)^2 + 3v^2 = 0 mod p. Since -3 is not a quadratic residue mod p ( remember that p =2 mod 3) , we must have v=0=u.(II)
Also, I don't lost in this part. Why do we need to prove this? How did you get that u^2+uv+v^2 =0 (mod p)?

Thank you!
 
  • #6
336
0
Assuming that [tex]1^3, 2^3, ..., (p-1)^3[/tex] form a reduced residue system mod p, does this always imply that [tex]0^3, 1^3, 2^3, ..., (p-1)^3[/tex] will form a complete residue system mod p? Why?
Yes, 0 is the only number missing.
Also, I don't lost in this part. Why do we need to prove this? How did you get that u^2+uv+v^2 =0 (mod p)?
I thought it safe to show that distinct values of xi can't correspond to the same quadratic residue. If they did, u^3+17 = v^3 +17 mod p . As p can't divide u-v &
u^3 -v^3 = (u-v)(u^2+uv+v^2 ) , we must have u^2+uv+v^2 =0 mod p.
 

Related Threads for: Elliptic Curve y^2 = x^3 +17; show N_p = p

  • Last Post
Replies
11
Views
3K
  • Last Post
Replies
1
Views
2K
Replies
1
Views
2K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
10
Views
3K
  • Last Post
Replies
7
Views
9K
  • Last Post
Replies
1
Views
2K
Top