Division by 3 on elliptic curve There is a classical theorem (cf. Theorem 4.1 on Husemoller "Elliptic Curve" book) that states conditions on the coordinates of a point P in an elliptic curve to be twice another point. The result is the following:
Theorem: Let $E$ be an elliptic curve defined over a field $K$ by the equation
$$
E:y^2=(x-\alpha)(x-\beta)(x-\gamma),\quad\mbox{with $\alpha,\beta,\gamma\in K$}. 
$$
For $(x',y')\in E(K)$ there exists $(x,y)\in E(K)$ with $2(x,y)=(x',y')$ if and only if $x'-\alpha$, $x'-\beta$ and $x'-\gamma$ are squares.
I would like to know if there is something similar for 3. That is, condition on the coordinates $(x',y')\in E(K)$ such that there exists $(x,y)\in E(K)$ with $3(x,y)=(x',y')$.
 A: In this paper by Ed Schaefer and myself, there is a reasonably explicit description of `3-descent' on an elliptic curve. There is a somewhat more detailed version of the paper here.
Assuming that your curve $E$ over $K$ is such that the Galois action on the points of order 3 is transitive, you look at the field $L = K(P_0)$, where $P_0$ is any point of order 3 on $E$. Then $P_0 = (\xi,\eta) \in E(K)$ and you can consider the tangent line $y = \lambda x + \mu$ at this point $P_0$. The map
$$E(K) \longrightarrow L^\times/L^{\times 3}, \qquad P \longmapsto f(P) = y(P) - \lambda x(P) - \mu$$
(modulo $L^{\times 3}$, where $L^{\times 3}$ means the subgroup of cubes) has kernel $3 E(K)$. This means that $P$ is divisible by 3 in $E(K)$ if and only if ($P = O$ or) $f(P)$ is a cube in $L$.
This is in fact the correct generalization of Joe's reply (for $m=3$) to the case when you don't have full rational 3-torsion: $f$ is the correctly scaled function with divisor $3(P_0) - 3(O)$, and working over $L$ basically means that we look at all the $f$'s for the various choices of $P_0$ at the same time.
When the Galois action is not transitive, you may have to consider two such functions $f$ (such that the orbits of the corresponding points generate $E[3]$ and have total cardinality not a multiple of 3).
A: A similar criterion, although more complicated, can be obtained using division polynomials. Let $P'=(x',y') \in E(K)$ be the given point. Then $P'=3P$, for some $P=(x,y)$ if and only if $$(x',y')=\left(\frac{\phi_3(x)}{\psi_3^2(x)}, \frac{\omega_3(x)}{\psi_3^3(x)} \right),$$
where $\phi_3, \psi_3$ and $\omega_3$ are defined as in http://en.wikipedia.org/wiki/Division_polynomials
So the question can be rephrased to asking whether the polynomial $\phi_3(x)-x'\psi_3^2(x)$ (note that $\psi_3(x)=0$ will hold only if  $P'=O$) has a $K$-rational root such that the corresponding $y$-coordiante is defined over $K$. This polynomial will be a degree 9 polynomial whose roots correspond to the $x$-coordinates of the 9 solutions (in $E(\overline K )$) of the equation $3P=P'$. 
The upside of this criterion is that you do not need any $3$-torsion in $E(K)$.
A: The fact that you quote comes from the Kummer sequence. Let $G_K=\text{Gal}(\bar K/K)$. Then one gets
$$
  E(K)/2E(K) \hookrightarrow  H^1(G_K,E[2]) = \text{Hom}(G_K,\mathbb{Z}/2\mathbb{Z}\times\mathbb{Z}/2\mathbb{Z})
    \cong K^*/(K^*)^2 \times K^*/(K^*)^2.
$$
This works because you're taking a curve for which all of the $2$-torsion is rational. You can do something similar if all of the $m$ torsion is rational, yielding
$$
  E(K)/mE(K) \hookrightarrow  H^1(G_K,E[m]) = \text{Hom}(G_K,\mathbb{Z}/m\mathbb{Z}\times\mathbb{Z}/m\mathbb{Z})
    \cong K^*/(K^*)^m \times K^*/(K^*)^m.
$$
(Note that the assumption that the $m$ torsion is rational implies that $K$ contains the $m$'th roots of unity, which is why the last isomorphism is okay.) From this one can in principle derive two functions $F$ and $G$ on $E$ with the property that $P$ is $m$ times a point if and only if $F(P)$ and $G(P)$ are $m$'th powers. But I don't know a reference offhand.
This may be in Husemoller's book, or you can find it in Chapter X of my Arithmetic of Elliptic Curves.
