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

Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last
• Mar 29th 2010, 10:08 PM
kingwinner
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]
• Mar 30th 2010, 04:32 AM
tonio
Quote:

Originally Posted by kingwinner
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
• Mar 30th 2010, 10:41 AM
kingwinner
Quote:

Originally Posted by tonio
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!
• Mar 30th 2010, 11:06 AM
tonio
Quote:

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
• Mar 30th 2010, 11:09 AM
kingwinner
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!
• Mar 30th 2010, 01:55 PM
chiph588@
Quote:

Originally Posted by kingwinner
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.
• Mar 30th 2010, 08:03 PM
kingwinner
Quote:

Originally Posted by chiph588@
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?

Quote:

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! :)
• Mar 30th 2010, 08:11 PM
chiph588@
Quote:

Originally Posted by kingwinner
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\}$

Quote:

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$
• Mar 30th 2010, 08:17 PM
kingwinner
Quote:

Originally Posted by chiph588@
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!
• Mar 30th 2010, 08:20 PM
chiph588@
Quote:

Originally Posted by kingwinner
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\}$
• Mar 30th 2010, 08:39 PM
kingwinner
Quote:

Originally Posted by chiph588@
$\{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?
• Mar 30th 2010, 08:43 PM
chiph588@
Quote:

Originally Posted by kingwinner
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?
• Mar 30th 2010, 09:47 PM
kingwinner
Quote:

Originally Posted by chiph588@
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! :)
• Mar 30th 2010, 10:07 PM
kingwinner
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?
• Mar 30th 2010, 10:31 PM
chiph588@
Quote:

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 ${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}$.
Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last