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

1. ## 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 $\displaystyle y^2 = x^3 + 17$. Prove that $\displaystyle 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 $\displaystyle 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]

2. Originally Posted by kingwinner
Suppose that p is an odd prime and p≡2 (mod 3). Let E be the elliptic curve defined by $\displaystyle y^2 = x^3 + 17$. Prove that $\displaystyle 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 $\displaystyle 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 $\displaystyle \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 $\displaystyle \{x^3\;;\;x\in\mathbb{F}_p\}=\mathbb{F}_p$ , and from here

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

Tonio

3. Originally Posted by tonio
Not having a background in abstract algebra is a huge handicap in this kind of problems: how come?! Anyway:

Putting $\displaystyle \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 $\displaystyle \{x^3\;;\;x\in\mathbb{F}_p\}=\mathbb{F}_p$ , and from here

it follows that $\displaystyle \{x^3+17\;;\;x\in\mathbb{F}_p\}=\mathbb{F}_p$ ...try to take it from here, taking into account that there exist exactly $\displaystyle \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!

4. Originally Posted by kingwinner
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

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

6. Originally Posted by kingwinner
Suppose that p is an odd prime and p≡2 (mod 3). Let E be the elliptic curve defined by $\displaystyle y^2 = x^3 + 17$. Prove that $\displaystyle 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 $\displaystyle 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 $\displaystyle (3,p-1)=1$, we have $\displaystyle \{1^3,2^3,\cdots,(p-1)^3\} = \{1,2,\cdots,p-1\}$.

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

So let's simplify things here.
Solving

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

Is the same as solving

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

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

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

3.) $\displaystyle y^2\equiv x\mod{p}$, where $\displaystyle 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 $\displaystyle \frac{p-1}{2}$ total QR.

Enumerate the above and we're done.

Edit: This is what Tonio did, just explained in simpler terms.

7. Originally Posted by chiph588@
Since $\displaystyle (3,p-1)=1$, we have $\displaystyle \{1^3,2^3,\cdots,(p-1)^3\} = \{1,2,\cdots,p-1\}$.

Also it's easy to see $\displaystyle \{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, $\displaystyle 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 $\displaystyle \{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.) $\displaystyle y^2\equiv 0\mod{p}$

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

3.) $\displaystyle y^2\equiv x\mod{p}$, where $\displaystyle 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 $\displaystyle \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!

8. Originally Posted by kingwinner
I understand this part, but I don't understand your next line. Why is it true that $\displaystyle \{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 $\displaystyle \{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 $\displaystyle N_p=2\left(\frac{p-1}{2}\right)+1 = p$

9. Originally Posted by chiph588@
Sorry, I meant to say $\displaystyle \{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 $\displaystyle 1^3, 2^3, ..., (p-1)^3$ form a REDUCED residue system mod p, but from here, how can we prove that {$\displaystyle 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!

10. Originally Posted by kingwinner
OK, then these two are both complete residue systems mod p. Makes sense.

I understand up to the point that $\displaystyle 1^3, 2^3, ..., (p-1)^3$ form a REDUCED residue system mod p, but from here, how can we prove that {$\displaystyle 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!
$\displaystyle \{0^3,1^3,\cdots,(p-1)^3\} = \{0,1,\cdots,p-1\}$

11. Originally Posted by chiph588@
$\displaystyle \{0^3,1^3,\cdots,(p-1)^3\} = \{0,1,\cdots,p-1\}$
If $\displaystyle 1^3, 2^3, ..., (p-1)^3$ form a reduced residue system mod p, does this always imply that $\displaystyle 0^3, 1^3, 2^3, ..., (p-1)^3$ will form a complete residue system mod p? Why?

12. Originally Posted by kingwinner
If $\displaystyle 1^3, 2^3, ..., (p-1)^3$ form a reduced residue system mod p, does this always imply that $\displaystyle 0^3, 1^3, 2^3, ..., (p-1)^3$ form a complete residue system mod p? Why?
Well... $\displaystyle 0^3=0$ and $\displaystyle \{1^3,2^3,\cdots,(p-1)^3\}=\{1,2,\cdots,p-1\}$

What does this tell you?

13. Originally Posted by chiph588@
Well... $\displaystyle 0^3=0$ and $\displaystyle \{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 $\displaystyle 1^3, 2^3, ..., (p-1)^3$, so no two elements in {$\displaystyle 0^3, 1^3, 2^3, ..., (p-1)^3$} are congruent to each other and this set has exactly p elements, therefore {$\displaystyle 0^3, 1^3, 2^3, ..., (p-1)^3$} is a complete residue system mod p.

Thanks!

14. 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 $\displaystyle {b_1}^3$ ≡ $\displaystyle {b_2}^3$ (mod p) => $\displaystyle b_1$ ≡ $\displaystyle b_2$ (mod p) ? If so, how can we prove it?

15. Originally Posted by kingwinner
So this problem is solved, but just out of curiosity...
Is it true that if gcd(3,p-1)=1, then $\displaystyle {b_1}^3$ ≡ $\displaystyle {b_2}^3$ (mod p) => $\displaystyle b_1$ ≡ $\displaystyle 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 $\displaystyle b_1,b_2\not|p$ and $\displaystyle g$ is a primitive root ($\displaystyle b_1\equiv0\mod{p}$ is trivial).

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

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

So $\displaystyle b_2\equiv g^m=g^{n+a(p-1)} \equiv 1\cdot g^n\equiv b_1\mod{p}$.

Page 1 of 2 12 Last