Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Mar 30, 2010 #1
    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.)
  2. jcsd
  3. Mar 30, 2010 #2
    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.
  4. Mar 30, 2010 #3
    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: Mar 30, 2010
  5. Mar 30, 2010 #4
    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.
  6. Mar 31, 2010 #5
    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?

    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!
  7. Mar 31, 2010 #6
    Yes, 0 is the only number missing.
    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook