If $A$ is finitely generated, the structure theorem for finitely generated modules over a principal ideal domain immediately makes $A/nA$ finite.

Conversely, first replace the given height by a quadratic one. SetCondition (ii) makes this limit converge and givesThus $\hat{h}$ still has finite bounded subsets. Condition (i) also gives a global lower bound for $h$, so $\hat{h}\ge 0$. Applying condition (iii) to $2^{r}P,2^{r}Q$, dividing by $4^r$ and passing to the limit gives one direction of the parallelogram identity. Applying the same inequality to $P+Q$ and $P-Q$, and using $\hat{h}(2P)=4\hat{h}(P)$, gives the reverse direction. Henceand induction yields $\hat{h}(mP)=m^2\hat{h}(P)$ for every integer $m$.

Now suppose $A/nA$ is finite and choose representatives $R_1,\dots ,R_s$. Put $R={\max }_i\hat{h}(R_i)$. For any $P$, write $P=nQ+R_i$. Nonnegativity and the parallelogram identity giveso, since $n\ge 2$,Repeated division modulo $nA$ therefore reaches the finite set $B=\{P:\hat{h}(P)\le R+1\}$. Reversing the recursion expresses every element of $A$ using $B$ and the finitely many $R_i$. This is the height descent lemma, and proves

The natural maphas finite image by hypothesis. It remains to bound its kernel. If $P\in E(K)$ becomes $nQ$ for $Q\in E(L)$, thenis a one-cocycle for $G=\mathrm{Gal}(L/K)$. Changing $Q$ by an $n$-torsion point changes this cocycle by a coboundary, producing a well-defined map from the kernel toIf its cohomology class is zero, subtracting the corresponding torsion point from $Q$ makes $Q$ Galois fixed, so $P\in nE(K)$. The map is therefore injective. Both $G$ and $E(L)[n]$ are finite, so this group cohomology set is finite. A finite kernel and finite image give

An integral Weierstrass equation has good reduction outside the finitely many primes dividing its nonzero discriminant. This proves finiteness of the set of bad primes. To prove finiteness of rational torsion, choose two distinct good primes. The reduction of torsion points on an elliptic curve injects each primary component at a good prime of different residue characteristic, so the two finite reduced point groups bound every primary component of $E(\mathbb{Q}{)}_{\mathrm{tors}}$.

Forthe displayed equation is minimal andIts bad primes are therefore exactlyThe good reductions at $11$ and $13$ haveTheir coprime orders exclude every rational torsion primary component, including the residue-characteristic components by using the other prime. Hence

For a minimal integral Weierstrass equation, let $\tilde{E}$ be the reduced cubic and ${\tilde{E}}_{\mathrm{ns}}(k)$ its nonsingular points, with their induced group law. Define the filtration of elliptic-curve points over a local field byandThe parameter $z=-x/y$ identifies $E_1(K)$ with the formal group of an elliptic curve on $\pi {\mathcal{O}}_K$. Part (a) therefore gives $E_1(K)[n]=0$. Reduction restricts to the exact sequenceIts restriction to $n$-torsion has trivial kernel, yielding the injection

A one-dimensional commutative formal group law over ${\mathcal{O}}_K$ is a power series $F(X,Y)\in {\mathcal{O}}_K[[X,Y]]$ satisfyingA morphism $h:\mathcal{F}\to \mathcal{G}$ is a series $h(T)\in T{\mathcal{O}}_K[[T]]$ satisfyingIf $h(T)=uT+O(T^2)$, the invertible morphism criterion for formal group laws says that $h$ is an isomorphism whenever $u\in {\mathcal{O}}_K^{\times }$. Indeed, recursive coefficient comparison constructs a unique compositional inverse $j(T)$; applying $j$ to the morphism identity shows that $j$ is a morphism in the opposite direction.

The multiplication series hasSince $p\nmid n$, its linear coefficient is a unit, so $[n{]}_{\mathcal{F}}$ is an automorphism of the group $\mathcal{F}(\pi {\mathcal{O}}_K)$. Its kernel is therefore zero, and

For $E:y^2=x^3+3$, direct counting givesNeither group order is divisible by $17$, so neither group contains a point of order $17$.

At $p=17$ the Frobenius trace is zero. The elliptic-curve point count over a finite field has trace recurrenceFor every $n\ge 1$, this order is congruent to one modulo $17$. Consequently $E({\mathbb{F}}_{17^n})$ has no point of order $17$ for any $n$.

At $p=31$, the trace is $a=31+1-43=-11$. On $E[17]$, Frobenius has characteristic polynomialIts discriminant is $14$, a nonsquare in ${\mathbb{F}}_{17}$, so its two distinct eigenvalues lie in ${\mathbb{F}}_{17^2}^{\times }$. Their orders divide $17^2-1=288$, whence ${\pi }^{288}=1$ on $E[17]$. Thus all of $E[17]$ is rational over ${\mathbb{F}}_{31^{288}}$, and in particular a point of order $17$ exists over some extension with $n\ge 2$.

The Hasse theorem for elliptic curves states that, for an elliptic curve over ${\mathbb{F}}_q$,Let $\pi$ be the Frobenius isogeny of an elliptic curve and put $a=q+1-\#E({\mathbb{F}}_q)$. The fixed points of $\pi$ are $E({\mathbb{F}}_q)$, and $1-\pi$ is separable, soHence the trace of an elliptic-curve endomorphism iswhile $\mathrm{deg}\pi =q$.

The degree on $\mathrm{End}(E)$ is a nonnegative quadratic form. Polarization and the identities for the dual isogeny give, for integers $m,n$,If $a^2>4q$, this real binary quadratic form is indefinite. An open cone on which it is negative contains a nonzero rational point and therefore a nonzero integer point, contradicting nonnegativity of isogeny degree. Thus $a^2\le 4q$, which is exactly the claimed inequality.

Let $E$ be a smooth plane cubic whose identity $O$ is an inflection point. A line through $P$ and $Q$, using the tangent when $P=Q$, has a third intersection $R$ counted with multiplicity. The chord-and-tangent group law defines $P+Q$ by drawing the line through $R$ and $O$ and taking its third intersection.

The clean verification of the group axioms uses divisors. The line at infinity meets a Weierstrass cubic in $3(O)$, so three collinear points $P,Q,R$ satisfyConsequently the mapsends the chord-and-tangent construction to addition of divisor classes. The principal divisor criterion on an elliptic curve shows that this map is bijective. Associativity and commutativity therefore follow from the abelian group law on ${\mathrm{Pic}}^0(E)$. The tangent convention handles repeated intersections, $O$ represents the zero class, and the third point on the line through $P$ and $O$ represents the inverse of $P$. Hence all group axioms hold.

We give the Agrawal–Biswas primality test, which has one-sided error. Small inputs and perfect powers can first be recognized deterministically. For every remaining integer $n$, put $d=\lceil 4{\log }_{2}n\rceil$ and choose a uniformly random monic polynomialUsing repeated squaring in the quotient ring $(\mathbb{Z}/n\mathbb{Z})[X]/(r)$, test the identityThis takes time polynomial in $\log n$ because every intermediate polynomial has degree below $d=O(\log n)$.

If $n$ is prime, the intermediate binomial coefficients are divisible by $n$, so the identity always holds. Now suppose that $n$ is composite and is not a prime power. Choose a prime divisor $p$ and write $n=p^{a}m$ with $p\nmid m$ and $m>1$. Over ${\mathbb{F}}_p$,because an intermediate coefficient equal to $m$ is nonzero modulo $p$. Henceis a nonzero polynomial of degree below $n$ over ${\mathbb{F}}_p$.

Reduction of random $r$ modulo $p$ is uniform among the $p^d$ monic degree-$d$ polynomials. The polynomial $F$ has at most $n/d$ distinct monic irreducible factors of degree $d$. On the other hand, the number $I_p(d)$ of monic irreducibles of degree $d$ obeys the standard lower boundWhenever $r\mathrm{mod}p$ is one of these irreducibles but does not divide $F$, the tested congruence fails. Thus one trial detects compositeness with probability at leastafter the finitely many small $n$ are handled directly. Repeating $2d$ times makes the probability of missing a composite less than $(1-1/(2d){)}^{2d}<1/2$, while a prime is never rejected. Therefore compositeness is in RP, and primality testing is in

First suppose $L\in \mathbf{RP}\cap \mathbf{co}\text{-}\mathbf{RP}$. Run the RP algorithm for $L$ and the RP algorithm for its complement with fresh random bits. If the first accepts, output one; if the second accepts, output zero; otherwise repeat. Neither output can be wrong, and on every input the appropriate algorithm accepts in each round with probability at least $1/2$. The number of rounds is dominated by a geometric distribution of mean two, so this is an always-correct algorithm with polynomial expected running time.

Conversely, let $T$ be always correct when it halts and have expected running time at most $p(n)$. Run it for $2p(n)$ steps. Markov inequality givesAccept exactly when $T$ halts and outputs one; this is an RP algorithm for $L$. Accepting exactly when it halts and outputs zero is an RP algorithm for the complement. Thereforeis equivalent to zero-error expected polynomial time.

A language $L$ belongs to RP when a polynomial-time randomized algorithm rejects every $x\notin L$ and accepts every $x\in L$ with probability at least $1/2$.

Amplify the algorithm on length-$n$ inputs with $n+1$ independent repetitions, accepting if any repetition accepts. Its error on each positive input is at most $2^{-(n+1)}$, while it still never accepts a negative input. Choose all random bits for all repetitions in advance. By the union bound, the probability that this one fixed choice fails on at least one of the at most $2^n$ positive strings is at mostThus some random string works simultaneously for every input of length $n$. Hardwire that string into the polynomial-time computation and compile it into a Boolean circuit. The resulting polynomial-size circuit family decides $L$, proving

Yes. The usual collapse relativizes because every machine involved receives the same oracle $A$. Induct on the levels of the polynomial hierarchy. The hypothesis givesIf the preceding level is contained in ${\mathbf{P}}^A$, then its oracle queries can be simulated in polynomial time with oracle $A$. A nondeterministic machine for the next existential level is therefore only an ${\mathbf{NP}}^A$ machine, hence a ${\mathbf{P}}^A$ machine by hypothesis. Complements give the corresponding universal level. The induction yields

This is the Karp–Lipton theorem. It is enough to place ${\Pi }_2^{\mathbf{P}}$ inside ${\Sigma }_2^{\mathbf{P}}$. Let $L\in {\Pi }_2^{\mathbf{P}}$, so for a polynomial-time predicate $R$ and polynomially bounded strings,The NP search problem that receives $(x,y)$ and seeks such a $z$ has, by part (i), a polynomial-size circuit family producing a valid witness whenever one exists. For each input length there is therefore a polynomial-size circuit $C$ such that, for every relevant $x,y$, existence of a witness implies $R(x,y,C(x,y))$.

Consequentlywhere the existentially guessed circuit description has polynomial length and evaluation of $C$ is polynomial time. This is a ${\Sigma }_2^{\mathbf{P}}$ description. Hence ${\Pi }_2^{\mathbf{P}}\subseteq {\Sigma }_2^{\mathbf{P}}$; complementation gives the reverse inclusion, and merging adjacent equal quantifier blocks collapses every higher level. Thus the polynomial hierarchy satisfies

Let $V(x,w)$ be a polynomial-time verifier for $f\in \mathbf{NP}$, with witnesses of length $p(|x|)$. Consider the prefix languageThis language lies in NP, so the assumption $\mathbf{NP}\subseteq \mathbf{P}/\mathrm{poly}$ supplies a polynomial-size circuit family deciding $B$.

Apply the usual search-to-decision reduction. Starting with the empty prefix, append zero if the circuit says that some accepting witness has that extended prefix; otherwise append one. Repeat for $p(n)$ positions. Composing the polynomially many copies of the decision circuit produces a polynomial-size circuit $C_n$. Whenever $f(x)=1$, at least one accepting extension exists at every step, so the final string $C_n(x)$ satisfiesOn negative inputs the output may be arbitrary, as required.

Membership follows from $\mathbf{NL}=\mathbf{co}\text{-}\mathbf{NL}$. A directed graph is not strongly connected exactly when there is a pair $(u,v)$ for which $v$ is not reachable from $u$. Guessing the pair and using the NL procedure for non-reachability puts non-strong-connectivity in NL, hence strong connectivity is in co-NL and therefore in NL.

For NL-hardness, reduce directed reachability. Given $(G,s,t)$, form $G^{\prime }$ by retaining all edges of $G$, adding $v\to s$ for every vertex $v$, and adding $t\to v$ for every vertex $v$. If $t$ is reachable from $s$ in $G$, then any $u$ reaches any $v$ in $G^{\prime }$ alongConversely, if $G^{\prime }$ is strongly connected then $s$ reaches $t$. A simple $s$-to-$t$ path cannot use an added edge out of $t$ before arriving at $t$, and every added edge into $s$ merely returns the path to its starting vertex; deleting the resulting cycle leaves an $s$-to-$t$ path made from edges of $G$. The construction is computable in logarithmic space, so deciding strong connectivity is

It suffices to recognize non-reachability in NL, since directed reachability is NL-complete. Let $c_k$ be the number of vertices reachable from $s$ by a directed path of length at most $k$. Clearly $c_0=1$. The inductive counting argument computes and verifies $c_{k+1}$ from $c_k$ using logarithmic space.

For each vertex $v$, reachability within $k+1$ steps has an NL certificate: guess such a path. Non-reachability within $k+1$ steps can be certified relative to the trusted value $c_k$ by enumerating vertices $u$, exhibiting paths of length at most $k$ to exactly $c_k$ distinct vertices, and checking that none is $v$ or has an edge to $v$. Because there are exactly $c_k$ reachable vertices, this list cannot omit a reachable predecessor. Counters, vertex names and one guessed path need only logarithmic space. Repeating this check in a fixed vertex order and counting the positive cases produces the exact $c_{k+1}$.

After $|V|-1$ rounds, the procedure knows the number of all vertices reachable from $s$. It accepts non-reachability of $t$ after certifying, by the same complete enumeration, that $t$ is absent. Thus the complement of directed reachability belongs to NL. Since every NL language reduces to reachability and log-space reductions are closed under complementation, this proves the Immerman–Szelepcsényi theorem