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

[kingwinner]

Theorem: 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$$. Then $$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 that $$N_p = p$$?
Any help is greatly appreciated! :) (If possible, please explain in simpler terms. In particular, I have no background in abstract algebra.)

 

[Eynstone]

Theorem: 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$$. Then $$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.]

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.

 

[kingwinner]

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 {x³ +17: x=0,1,2,...,p-1} a COMPLETE residue system?

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

Thanks for your help! :)

 

[Eynstone]

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.

 

[kingwinner]

Assuming that $$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?

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!

 

[Eynstone]

Assuming that $$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?

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.