[proofplan] We view $E(\mathbb{F}_p)$ as a finite group under the elliptic-curve addition law. The point $P$ generates a cyclic subgroup $H = \langle P\rangle$, whose cardinality is exactly $\operatorname{ord}(P)$. We then prove the needed finite-group divisibility directly by partitioning $E(\mathbb{F}_p)$ into left cosets of $H$, each of which has the same cardinality as $H$. [/proofplan]

[step:Identify the finite ambient group and the cyclic subgroup generated by $P$]Because $p \ne 2,3$ and $E: y^2=x^3+ax+b$ is an [elliptic curve](/page/Elliptic%20Curve) over $\mathbb{F}_p$, the cubic is nonsingular; equivalently $4a^3+27b^2 \ne 0$ in $\mathbb{F}_p$. Therefore the usual elliptic-curve addition law makes the set of rational points into an abelian [group](/page/Group). Let $G := E(\mathbb{F}_p)$ denote this group, with operation written additively and identity element $O$. Since \begin{align*} E(\mathbb{F}_p) \subset \mathbb{F}_p^2 \cup \{O\}, \end{align*} the set $G$ is finite. Fix $P \in G$. Define the cyclic subgroup generated by $P$ by \begin{align*} H := \langle P\rangle = \{nP : n \in \mathbb{Z}\} \subset G. \end{align*} Because $G$ is finite, $H$ is finite. By definition, $\operatorname{ord}(P)$ is the cardinality of the cyclic subgroup generated by $P$, equivalently the least positive integer $m$ such that $mP = O$. Hence \begin{align*} |H| = \operatorname{ord}(P). \end{align*}[/step]

[guided]We first isolate the group-theoretic object to which the argument applies. Since $p \ne 2,3$ and $E: y^2=x^3+ax+b$ is an [elliptic curve](/page/Elliptic%20Curve) over $\mathbb{F}_p$, the displayed short Weierstrass equation is nonsingular; equivalently $4a^3+27b^2 \ne 0$ in $\mathbb{F}_p$. This nonsingularity hypothesis is exactly what permits the usual elliptic-curve addition law on rational points. Define $G := E(\mathbb{F}_p)$ to be the resulting abelian [group](/page/Group), with operation written additively. The identity element is the point at infinity $O$. Why is $G$ finite? A point of $E(\mathbb{F}_p)$ is either $O$ or a pair $(x,y) \in \mathbb{F}_p^2$ satisfying $y^2 = x^3 + ax + b$. Therefore \begin{align*} E(\mathbb{F}_p) \subset \mathbb{F}_p^2 \cup \{O\}. \end{align*} Since $\mathbb{F}_p$ has $p$ elements, the set $\mathbb{F}_p^2 \cup \{O\}$ is finite, so $G$ is finite. Now fix $P \in G$. The subgroup generated by $P$ is \begin{align*} H := \langle P\rangle = \{nP : n \in \mathbb{Z}\}. \end{align*} This is a subgroup of $G$ because sums and inverses of integer multiples of $P$ are again integer multiples of $P$. Since $H \subset G$ and $G$ is finite, $H$ is finite. The order $\operatorname{ord}(P)$ is precisely the number of distinct elements in this cyclic subgroup; equivalently, it is the least positive integer $m$ for which $mP = O$. Thus \begin{align*} |H| = \operatorname{ord}(P). \end{align*}[/guided]

[step:Partition $G$ into cosets of $H$]For each $Q \in G$, define the coset of $H$ with representative $Q$ by \begin{align*} Q + H := \{Q + R : R \in H\}. \end{align*} The family of distinct cosets of $H$ in $G$ partitions $G$. Indeed, every $Q \in G$ lies in $Q+H$ because $O \in H$, and if two cosets $Q_1+H$ and $Q_2+H$ intersect, then there exist $R_1,R_2 \in H$ such that \begin{align*} Q_1 + R_1 = Q_2 + R_2. \end{align*} Rearranging in the group $G$ gives \begin{align*} Q_2 = Q_1 + (R_1 - R_2). \end{align*} Since $R_1 - R_2 \in H$, it follows that $Q_2 \in Q_1+H$, and therefore $Q_2+H \subset Q_1+H$. The same argument with $Q_1$ and $Q_2$ interchanged gives $Q_1+H \subset Q_2+H$, so the two cosets are equal.[/step]

[guided]The next task is to turn the subgroup $H$ into a counting device. For each $Q \in G$, define the coset of $H$ with representative $Q$ by \begin{align*} Q + H := \{Q + R : R \in H\}. \end{align*} This notation is meaningful because the group operation on $G=E(\mathbb{F}_p)$ is written additively. We prove that the distinct cosets partition $G$. First, every $Q \in G$ belongs to its own coset $Q+H$, because the identity element $O$ lies in $H$ and $Q=Q+O$. Thus the union of all cosets is all of $G$. It remains to prove that two cosets are either disjoint or equal. Suppose $Q_1+H$ and $Q_2+H$ intersect. Then there is an element lying in both cosets, so there exist $R_1,R_2 \in H$ such that \begin{align*} Q_1 + R_1 = Q_2 + R_2. \end{align*} Using cancellation and inverses in the group $G$, we rearrange this equality as \begin{align*} Q_2 = Q_1 + (R_1 - R_2). \end{align*} Because $H$ is a subgroup, it is closed under subtraction, so $R_1-R_2 \in H$. Hence $Q_2 \in Q_1+H$. Now take any element $S \in Q_2+H$. By definition of the coset, there exists $R \in H$ such that $S=Q_2+R$. Since $Q_2=Q_1+(R_1-R_2)$, we get \begin{align*} S = Q_1 + ((R_1-R_2)+R). \end{align*} Again $H$ is closed under addition, so $(R_1-R_2)+R \in H$, and therefore $S \in Q_1+H$. This proves $Q_2+H \subset Q_1+H$. Interchanging the roles of $Q_1$ and $Q_2$ gives the reverse inclusion, so $Q_1+H=Q_2+H$. Therefore the distinct cosets form a partition of $G$.[/guided]

[step:Show every coset has exactly $|H|$ elements]Fix $Q \in G$. Define the translation map $\tau_Q: H \to Q+H$ by sending each $R \in H$ to $Q+R$. This map is surjective by the definition of $Q+H$. It is injective because if $R_1,R_2 \in H$ and $\tau_Q(R_1)=\tau_Q(R_2)$, then \begin{align*} Q+R_1 = Q+R_2, \end{align*} and cancellation in the group $G$ gives $R_1=R_2$. Hence $\tau_Q$ is a bijection, so \begin{align*} |Q+H| = |H|. \end{align*}[/step]

[guided]We now prove that every piece in the coset partition has the same size. Fix a representative $Q \in G$. Define the translation map $\tau_Q: H \to Q+H$ by $\tau_Q(R)=Q+R$ for each $R \in H$. The map is surjective because every element of $Q+H$ has the form $Q+R$ for some $R \in H$, which is exactly $\tau_Q(R)$. The map is injective because if $R_1,R_2 \in H$ satisfy $\tau_Q(R_1)=\tau_Q(R_2)$, then \begin{align*} Q+R_1 = Q+R_2. \end{align*} Adding the inverse of $Q$ to both sides in the group $G$ gives $R_1=R_2$. Thus $\tau_Q$ is both injective and surjective, hence a bijection from $H$ onto $Q+H$. A bijection preserves cardinality, so \begin{align*} |Q+H| = |H|. \end{align*} This is the counting fact that makes the final divisibility argument work: the finite group $G$ is split into disjoint blocks, and every block has exactly $|H|$ elements.[/guided]

[step:Count the cosets and obtain the divisibility]Since $G$ is finite, there are finitely many distinct cosets of $H$ in $G$. Let $k \in \mathbb{N}$ be the number of distinct cosets. By the partition established above and the equal-size result for cosets, \begin{align*} |G| = k|H|. \end{align*} Substituting $G = E(\mathbb{F}_p)$ and $|H| = \operatorname{ord}(P)$ gives \begin{align*} |E(\mathbb{F}_p)| = k\,\operatorname{ord}(P). \end{align*} Therefore \begin{align*} \operatorname{ord}(P) \mid |E(\mathbb{F}_p)|. \end{align*} This is the desired divisibility.[/step]

[guided]The distinct cosets of $H$ partition $G$, and $G$ is finite. Therefore there are finitely many distinct cosets. Let $k \in \mathbb{N}$ denote the number of distinct cosets. Because the cosets are disjoint and their union is $G$, the cardinality of $G$ is the sum of the cardinalities of these $k$ cosets. The previous step proves that each coset has cardinality $|H|$, so \begin{align*} |G| = k|H|. \end{align*} Now substitute the two identifications already established: $G=E(\mathbb{F}_p)$ and $|H|=\operatorname{ord}(P)$. This gives \begin{align*} |E(\mathbb{F}_p)| = k\operatorname{ord}(P). \end{align*} Since $k \in \mathbb{N}$, this equation says exactly that $\operatorname{ord}(P)$ divides $|E(\mathbb{F}_p)|$. Hence \begin{align*} \operatorname{ord}(P) \mid |E(\mathbb{F}_p)|. \end{align*} This proves the theorem.[/guided]