# Elliptic Curves - Proving that the group is not cyclic

I have a question from Stinson: 7.14. The question states:

Suppose that $$p > 3$$ is an odd prime, and $$a,b$$ is an element of $$\mathbb Z_p$$. Further, suppose that the equation $$x^3 + ax + b$$ is congruent to $$0$$ ($$\mod p$$) has 3 distinct roots in $$\mathbb Z_p$$. Prove that the corresponding elliptic curve group $$(E, +)$$ is not cyclic. Hint: Show that the points of order two generate a subgroup of $$(E, +)$$ that is isomorphic to $$\mathbb Z_2 \times\mathbb Z_2$$.

I've read through the elliptic curve material in the chapter preceding this question but I'm still a little hopeless. Can anyone explain or push me in the right direction on how to show/answer this?

I understand that points of order two (from the hint) follow the formula: $$P = \mathcal{O}$$ but I'm not sure how this relates.

## 1 Answer

Can anyone explain or push me in the right direction on how to show/answer this?

The first obvious thing to ponder is "what does it mean that a 'group is cyclic'? What properties does a cyclic group have, that noncyclic groups do not?"

(Broader hint: a cyclic group has a generator; noncyclic (finite) groups do not)

I understand that points of order two (from the hint) follow the formula: 2P = 0 but I'm not sure how this relates.

It relates quite a bit, actually. Can a cyclic group have two different elements of order 2?

Update: since Dexter has solved the problem, I'll lay out the proof I was originally trying to suggest.

One fundamental property of all finite groups is that, if $$n$$ is the number of group elements, we have $$xP = (x \bmod n)P$$ (for any integer $$x$$ and any element $$P$$).

In addition, a finite group is cyclic if it has a generator, that is, an element $$G$$ for which all elements can be expressed as $$xG$$ (for some $$x$$). In addition, for any $$P$$, we always have $$xG = P$$ for some $$0 \le x < n$$. In particular, $$xG \ne 0$$ for any $$0 < x < n$$.

Now, for the group in question, we have two distinct elements $$P_1$$ and $$P_2$$, both of order two (actually, we have three, we only need two). That is, $$P_1 \ne P_2 \ne 0$$, and $$2P_1 = 2P_2 = 0$$.

Now, suppose the group is cyclic; if so, we have a generator $$G$$. We know $$P_1$$ can be expressed as $$P_1 = x_1G$$ for some $$0 \le x_1 < n$$. We also have $$2P_1 = 0$$, that is, $$2 (x_1 G) = (2 x_1)G = 0$$. We know that $$(2x_1)G = (2x_1 \bmod n)G$$, and if that is the neutral element, we must have $$2x_1 \bmod n = 0$$. The only value $$0 < x_1 < n$$ that can satisfy that is $$x_1 = n/2$$ (which implies that $$n$$ must be even).

However, by the same reasoning, if we have $$P_2 = x_2G$$, we have $$x_2 = n/2$$, but that would mean that $$P_1 = (n/2)G = P_2$$, and so the two points of order two were the same, but we know they aren't.

Hence, there cannot be a generator, and hence the group cannot be cyclic.

This proof may sound a bit lengthy, however, that's mostly because I spelled out the logic quite explicitly, listing the various assumed properties of groups. Once you get more acquainted with group theory, this logic would be more natural.

• So a group is cyclic if it contains an element that, when raised to powers, calculates all of the other elements of that group... So I have to show that the group (E, +) is not cyclic by showing it has no generators? – Dexter Mar 24 '20 at 21:25
• @Dexter: that would work - how could you use the existence of two elements of order two to show that there cannot be a generator? – poncho Mar 24 '20 at 21:26
• What is the group (E, +)? – Dexter Mar 24 '20 at 21:26
• Well I think that if two elements have both order two, would they have to equal because they both equal 0? Suppose 2P = 0 and 2Q = 0, that means 2P = 2Q => P = Q, but this can't be true correct? – Dexter Mar 24 '20 at 21:33
• The question says that the elliptic curve is mod p, which is an odd prime. If this is true, then the possible cycle length of generators is either 1 or of length p... Wouldn't this prove that the group is cyclic instead of not cyclic? – Dexter Mar 24 '20 at 21:35