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

**kingwinner** · March 29th 2010, 09:08 PM

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]

**tonio** · March 30th 2010, 03:32 AM

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

**kingwinner** · March 30th 2010, 09:41 AM

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!

**tonio** · March 30th 2010, 10:06 AM

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

**kingwinner** · March 30th 2010, 10:09 AM

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!

**chiph588@** · March 30th 2010, 12:55 PM

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.

**kingwinner** · March 30th 2010, 07:03 PM

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?

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!

**chiph588@** · March 30th 2010, 07:11 PM

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\}$

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$

**kingwinner** · March 30th 2010, 07:17 PM

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!

**chiph588@** · March 30th 2010, 07:20 PM

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\}$

**kingwinner** · March 30th 2010, 07:39 PM

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?

**chiph588@** · March 30th 2010, 07:43 PM

Originally Posted by kingwinner

If $1^3, 2^3, ..., (p-1)^3$ form a reduced residue system mod p, does this always imply that $<font color=$ 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?

**kingwinner** · March 30th 2010, 08:47 PM

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!

**kingwinner** · March 30th 2010, 09:07 PM

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?

**chiph588@** · March 30th 2010, 09:31 PM

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}$ .

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

LinkBack

Thread Tools

Display

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

Similar Math Help Forum Discussions

negative of point on elliptic curve

Elliptic Curve Group / Multiplication

The circle as a degenerate elliptic curve

Elliptic Curve

torsion for elliptic curve

Search Tags