Page 1 of 2 12 LastLast
Results 1 to 15 of 20

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

  1. #1
    Senior Member
    Joined
    Jan 2009
    Posts
    404

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

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

    Does anyone have any idea how to prove this?
    Any help is greatly appreciated! (If possible, please explain in simpler terms. In particular, I have no background in abstract algebra.)


    [also under discussion in math link forum]
    Last edited by kingwinner; March 29th 2010 at 09:31 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Quote Originally Posted by kingwinner View Post
    Suppose that p is an odd prime and p≡2 (mod 3). Let E be the elliptic curve defined by y^2 = x^3 + 17. Prove that N_p, the number of solutions mod p of the elliptic curve E, is exactly equal to p.
    [hint: if p is a prime, then 1^k, 2^k, ..., (p-1)^k form a reduced residue system (mod p) if and only if gcd(k, p-1)=1.]

    Does anyone have any idea how to prove this?
    Any help is greatly appreciated! (If possible, please explain in simpler terms. In particular, I have no background in abstract algebra.)

    [also under discussion in math link forum]

    Not having a background in abstract algebra is a huge handicap in this kind of problems: how come?! Anyway:

    Putting \mathbb{F}_p:=\mathbb{Z}\slash p\mathbb{Z}: the hint (a rather big one) together with the conditions on the prime p tell you that \{x^3\;;\;x\in\mathbb{F}_p\}=\mathbb{F}_p , and from here

    it follows that \{x^3+17\;;\;x\in\mathbb{F}_p\}=\mathbb{F}_p ...try to take it from here, taking into account that there exist exactly \frac{p+1}{2} quadratic residues modulo p, counting zero of course.

    Tonio
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Jan 2009
    Posts
    404
    Quote Originally Posted by tonio View Post
    Not having a background in abstract algebra is a huge handicap in this kind of problems: how come?! Anyway:

    Putting \mathbb{F}_p:=\mathbb{Z}\slash p\mathbb{Z}: the hint (a rather big one) together with the conditions on the prime p tell you that \{x^3\;;\;x\in\mathbb{F}_p\}=\mathbb{F}_p , and from here

    it follows that \{x^3+17\;;\;x\in\mathbb{F}_p\}=\mathbb{F}_p ...try to take it from here, taking into account that there exist exactly \frac{p+1}{2} quadratic residues modulo p, counting zero of course.

    Tonio
    hmm...sorry, I don't understand your notation at all...What is F_p? What is Z/pZ?

    Looking at {1,2,...,p-1}, I know that (p-1)/2 of these will be quadratic residues mod p, and (p-1)/2 of them will be quadratic nonresidues mod p. But how is this fact going to help?

    Also, I noted that if (x',y') is a solution, then (x',-y') is also a solution. Thus, the solutions occur in pairs unless when y'=0 .

    Thank you!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Quote Originally Posted by kingwinner View Post
    hmm...sorry, I don't understand your notation at all...What is F_p? What is Z/pZ?

    Looking at {1,2,...,p-1}, I know that (p-1)/2 of these will be quadratic residues mod p, and (p-1)/2 of them will be quadratic nonresidues mod p. But how is this fact going to help?

    Also, I noted that if (x',y') is a solution, then (x',-y') is also a solution. Thus, the solutions occur in pairs unless when y'=0 .

    Thank you!

    Sorry, I honestly cannot help you: if you don't even know the ring (field in this case, in fact) of residues modulo p I can't see how can somebody expect you to understand, let alone solve, this problem.
    Perhaps there's a way, but I don't know it.

    Tonio
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Jan 2009
    Posts
    404
    I have no background in groups, fields, and rings, and this is the kind of abstract algebra background that I don't have...unfortunately.

    I hope someone can explain without these concepts...

    Thank you!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by kingwinner View Post
    Suppose that p is an odd prime and p≡2 (mod 3). Let E be the elliptic curve defined by y^2 = x^3 + 17. Prove that N_p, the number of solutions mod p of the elliptic curve E, is exactly equal to p.
    [hint: if p is a prime, then 1^k, 2^k, ..., (p-1)^k form a reduced residue system (mod p) if and only if gcd(k, p-1)=1.]

    Does anyone have any idea how to prove this?
    Any help is greatly appreciated! (If possible, please explain in simpler terms. In particular, I have no background in abstract algebra.)


    [also under discussion in math link forum]
    Since  (3,p-1)=1 , we have  \{1^3,2^3,\cdots,(p-1)^3\} = \{1,2,\cdots,p-1\} .

    Also it's easy to see  \{1+17,2+17,\cdots,p-1+17\} = \{1,2,\cdots,p-1\} .

    So let's simplify things here.
    Solving

     y^2\equiv 0^3+17\mod{p}
     y^2\equiv 1^3+17\mod{p}
     \vdots
     y^2\equiv (p-1)^3+17\mod{p}

    Is the same as solving

     y^2\equiv 0\mod{p}
     y^2\equiv 1\mod{p}
     \vdots
     y^2\equiv p-1\mod{p}

    Now look at three cases:
    1.)  y^2\equiv 0\mod{p}

    2.)  y^2\equiv x\mod{p} , where  x is a quadratic residue.

    3.)  y^2\equiv x\mod{p} , where  x is a quadratic non-residue.

    For case 1, we have 1 solution.
    For case 3, there are no solutions by definition.
    For case 2, each QR has 2 solutions, and there are  \frac{p-1}{2} total QR.

    Enumerate the above and we're done.

    Edit: This is what Tonio did, just explained in simpler terms.
    Last edited by chiph588@; March 30th 2010 at 03:29 PM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member
    Joined
    Jan 2009
    Posts
    404

    Thumbs up

    Quote Originally Posted by chiph588@ View Post
    Since  (3,p-1)=1 , we have  \{1^3,2^3,\cdots,(p-1)^3\} = \{1,2,\cdots,p-1\} .

    Also it's easy to see  \{1+17,2+17,\cdots,p-1+17\} = \{1,2,\cdots,p-1\} .
    p≡2 (mod 3) => p-1≡1 (mod 3) => 3 does not divide p-1
    => gcd(3,p-1)=1 (since 3 is a prime)
    => by the hint, 1^3, 2^3, ..., (p-1)^3 form a reduced residue system mod p
    I understand this part, but I don't understand your next line. Why is it true that \{1+17,2+17,\cdots,p-1+17\} = \{1,2,\cdots,p-1\}? This is NOT a COMPLETE residue system mod p, so I don't think this is necessarily true?



    Now look at three cases:
    1.)  y^2\equiv 0\mod{p}

    2.)  y^2\equiv x\mod{p} , where  x is a quadratic residue.

    3.)  y^2\equiv x\mod{p} , where  x is a quadratic non-residue.

    For case 1, we have 1 solution.
    For case 3, there are no solutions by definition.
    For case 2, each QR has 2 solutions, and there are  \frac{p-1}{2} total QR.

    Enumerate the above and we're done.
    I understand this part, so using this part and assuming the part above that I don't understand, we have that N_p = [(p-1)/2] x 2 + 1 = p.
    But what do you mean by "enumerate the above"?

    Thanks a lot for your help!
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by kingwinner View Post
    I understand this part, but I don't understand your next line. Why is it true that \{1+17,2+17,\cdots,p-1+17\} = \{1,2,\cdots,p-1\}? This is NOT a COMPLETE residue system mod p, so I don't think this is necessarily true?
    Sorry, I meant to say  \{0+17,1+17,2+17,\cdots,p-1+17\} = \{0,1,2,\cdots,p-1\}

    But what do you mean by "enumerate the above"?
    I just meant to gather everything to notice that  N_p=2\left(\frac{p-1}{2}\right)+1 = p
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Senior Member
    Joined
    Jan 2009
    Posts
    404
    Quote Originally Posted by chiph588@ View Post
    Sorry, I meant to say  \{0+17,1+17,2+17,\cdots,p-1+17\} = \{0,1,2,\cdots,p-1\}
    OK, then these two are both complete residue systems mod p. Makes sense.

    I understand up to the point that 1^3, 2^3, ..., (p-1)^3 form a REDUCED residue system mod p, but from here, how can we prove that { x^3 +17: x=0,1,2,...,p-1} form COMPLETE residue system mod p?
    This is the part I'm struggling.

    Thanks for helping!
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by kingwinner View Post
    OK, then these two are both complete residue systems mod p. Makes sense.

    I understand up to the point that 1^3, 2^3, ..., (p-1)^3 form a REDUCED residue system mod p, but from here, how can we prove that { x^3 +17: x=0,1,2,...,p-1} form COMPLETE residue system mod p?
    This is the part I'm struggling.

    Thanks for helping!
     \{0^3,1^3,\cdots,(p-1)^3\} = \{0,1,\cdots,p-1\}
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Senior Member
    Joined
    Jan 2009
    Posts
    404

    Arrow

    Quote Originally Posted by chiph588@ View Post
     \{0^3,1^3,\cdots,(p-1)^3\} = \{0,1,\cdots,p-1\}
    If 1^3, 2^3, ..., (p-1)^3 form a reduced residue system mod p, does this always imply that 0^3, 1^3, 2^3, ..., (p-1)^3 will form a complete residue system mod p? Why?
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by kingwinner View Post
    If 1^3, 2^3, ..., (p-1)^3 form a reduced residue system mod p, does this always imply that 0^3, 1^3, 2^3, ..., (p-1)^3" alt="0^3, 1^3, 2^3, ..., (p-1)^3" /> form a complete residue system mod p? Why?
    Well...  0^3=0 and \{1^3,2^3,\cdots,(p-1)^3\}=\{1,2,\cdots,p-1\}

    What does this tell you?
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Senior Member
    Joined
    Jan 2009
    Posts
    404

    Post

    Quote Originally Posted by chiph588@ View Post
    Well...  0^3=0 and \{1^3,2^3,\cdots,(p-1)^3\}=\{1,2,\cdots,p-1\}

    What does this tell you?
    This tells me that 0 is not congruent to any of 1^3, 2^3, ..., (p-1)^3, so no two elements in { 0^3, 1^3, 2^3, ..., (p-1)^3} are congruent to each other and this set has exactly p elements, therefore { 0^3, 1^3, 2^3, ..., (p-1)^3} is a complete residue system mod p.

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Senior Member
    Joined
    Jan 2009
    Posts
    404

    Lightbulb

    So this problem is solved, but just out of curiosity...
    Is it true that if p is a prime and gcd(3,p-1)=1, then {b_1}^3 {b_2}^3 (mod p) => b_1 b_2 (mod p) ? If so, how can we prove it?
    Last edited by kingwinner; March 31st 2010 at 10:19 PM.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by kingwinner View Post
    So this problem is solved, but just out of curiosity...
    Is it true that if gcd(3,p-1)=1, then {b_1}^3 {b_2}^3 (mod p) => b_1 b_2 (mod p) ? If so, how can we prove it?
    Yes, the only proof I can think of off the top of my head uses primitive roots.

    Let's assume  b_1,b_2\not|p and  g is a primitive root (  b_1\equiv0\mod{p} is trivial).

    Then  b_1\equiv g^n,\;b_2\equiv g^m \mod{p} , so  g^{3n}\equiv g^{3m}\mod{p}\implies 3n\equiv 3m\mod{\phi(p)} .

    Since  (3,p-1)=1 \implies n\equiv m\mod{\phi(p)} \implies m=n+a(p-1)

    So  b_2\equiv g^m=g^{n+a(p-1)} \equiv 1\cdot g^n\equiv b_1\mod{p} .
    Last edited by chiph588@; March 31st 2010 at 12:11 PM.
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. negative of point on elliptic curve
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: November 11th 2011, 06:19 PM
  2. Elliptic Curve Group / Multiplication
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: September 18th 2011, 02:30 PM
  3. The circle as a degenerate elliptic curve
    Posted in the Higher Math Forum
    Replies: 15
    Last Post: July 8th 2011, 12:11 PM
  4. Elliptic Curve
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: July 7th 2011, 11:49 PM
  5. torsion for elliptic curve
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: October 31st 2009, 02:35 PM

Search Tags


/mathhelpforum @mathhelpforum