Appendix A
Number Theory


Basic results
Let n be a positive integer and let Zn be the set of integers mod n. It is a
group with respect to addition. We can represent the elements of Zn by the
numbers 0, 1, 2, . . . , n ’ 1. Let

Z— = {a | 1 ¤ a ¤ n, gcd(a, n) = 1}.
n


Then Z— is a group with respect to multiplication mod n.
n
Let a ∈ Z— . The order of a mod n is the smallest integer k > 0 such that
n
ak ≡ 1 (mod n). The order of a mod n divides φ(n), where φ is the Euler
φ-function.
Let p be a prime and let a ∈ Z— . The order of a mod p divides p ’ 1. A
p
primitive root mod p is an integer g such that the order of g mod p equals
p ’ 1. If g is a primitive root mod p, then every integer is congruent mod p
to 0 or to a power of g. For example, 3 is a primitive root mod 7 and

{1, 3, 9, 27, 81, 243} ≡ {1, 3, 2, 6, 4, 5} (mod 7).

There are φ(p ’ 1) primitive roots mod p. In particular, a primitive root mod
p always exists, so Z— is a cyclic group.
p
There is an easy criterion for deciding whether g is a primitive root mod
p, assuming we know the factorization of p ’ 1: If g (p’1)/q ≡ 1 (mod p) for
all primes q|p ’ 1, then g is a primitive root mod p. This can be proved by
noting that if g is not a primitive root, then its order is a proper divisor of
p ’ 1, hence divides (p ’ 1)/q for some prime q.
One way to ¬nd a primitive root for p, assuming the factorization of p ’ 1
is known, is simply to test the numbers 2, 3, 5, 6, . . . successively until a
primitive root is found. Since there are many primitive roots, one should be
found fairly quickly in most cases.
A very useful result in number theory is the following.


471

© 2008 by Taylor & Francis Group, LLC
472 APPENDIX A NUMBER THEORY

THEOREM A.1 (Chinese Remainder Theorem)
Let n1 , n2 , . . . , nr be positive integers such that gcd(ni , nj ) = 1 when i = j.
Let a1 , a2 , . . . , ar be integers. Then there exists an x such that

x ≡ ai (mod ni ) for all i.

The integer x is uniquely determined mod n1 n2 · · · nr .

For example, let n1 = 4, n2 = 3, n3 = 5 and let a1 = 1, a2 = 2, a3 = 3.
Then x = 53 is a solution to the simultaneous congruences

x≡1 x≡2 x≡3
(mod 4), (mod 3), (mod 5),

and any solution x satis¬es x ≡ 53 (mod 60).
Another way to state the Chinese Remainder Theorem is to say that if
gcd(ni , nj ) = 1 for i = j, then

Zn1 • · · · • Znr
Zn1 n2 ···nr

(see Appendix B for the de¬nition of •). This is an isomorphism of additive
groups. It is also an isomorphism of rings.




p-adic numbers
Let p be a prime number and let x be a nonzero rational number. Write
a
x = pr ,
b
where a, b are integers such that p ab. Then r is called the p-adic valuation
of x and is denoted by
r = vp (x).
De¬ne vp (0) = ∞. (The p-adic valuation is discussed in more detail in Sections
5.4 and 8.1.) The p-adic absolute value of x is de¬ned to be

|x|p = p’r .

De¬ne |0|p = 0.
For example,
1 11 1
1
12
’ 41
= , = 125, = .
35 4 250 2 81
2 5 3

The last example says that 1/2 and 41 are close 3-adically. Note that two
integers are close p-adically if and only if they are congruent mod a large
power of p.




© 2008 by Taylor & Francis Group, LLC
473
p-ADIC NUMBERS

The p-adic integers are most easily regarded as sums of the form

an pn , an ∈ {0, 1, 2, . . . , p ’ 1}.
n=0

Such in¬nite sums do not converge in the real numbers, but they do make
sense with the p-adic absolute value since |an pn |p ’ 0 as n ’ ∞.
Arithmetic operations are carried out just as with ¬nite sums. For example,
in the 3-adic integers,

(1 + 2 · 3 + 0 · 32 + · · · ) + (1 + 2 · 3 + 1 · 32 + · · · ) = 2 + 4 · 3 + 1 · 32 + · · ·
= 2 + 1 · 3 + 2 · 32 + · · ·

(where we wrote 4 = 1 + 3 and regrouped, or “carried,” to obtain the last
expression). If
x = ak pk + ak+1 pk+1 + · · ·
with ak = 0, then

’x = (p ’ ak )pk + (p ’ 1 ’ ak+1 )pk+1 + (p ’ 1 ’ ak+2 )pk+2 + · · · (A.1)

(use the fact that pk+1 + (p ’ 1)pk+1 + (p ’ 1)pk+2 + · · · = 0 because the sum
telescopes, so all the terms cancel). Therefore, p-adic integers have additive
inverses. It is not hard to show that the p-adic integers form a ring.
Any rational number with denominator not divisible by p is a p-adic integer.
For example, in the 3-adics,
’1
1
= ’(1 + 3 + 32 + · · · ) = 2 + 3 + 32 + · · · ,
=
1’3
2
where we used (A.1) for the last equality. In fact, it can be shown that if

x = n=0 an pn is a p-adic integer with a0 = 0, then 1/x is a p-adic integer.
The p-adic rationals, which we denote by Qp , are sums of the form

an pn ,
y= (A.2)
n=m

with m positive or negative or zero and with an ∈ {0, 1, . . . , p ’ 1}. If y ∈ Qp ,
then pk y is a p-adic integer for some integer k. The p-adic rationals form a
¬eld, and every rational number lies in Qp . If am = 0 in (A.2), then we de¬ne

|y|p = p’m .
vp (y) = m,

This agrees with the de¬nitions of the p-adic valuation and absolute value
de¬ned above when y is a rational number.
Another way to look at p-adic integers is the following. Consider sequences
of integers x1 , x2 , . . . such that

(mod pm )
xm ≡ xm+1 (A.3)




© 2008 by Taylor & Francis Group, LLC
474 APPENDIX A NUMBER THEORY

for all m ≥ 1. Since xm ≡ xk (mod pm ) for all k ≥ m, the base p expansions
for all xk with k ≥ m must agree through the pm’1 term. Therefore, the
sequence of integers xm determines an expression of the form

an pn ,
n=0

where
m’1
an pn (mod pm )
xm ≡
n=0

for all m. In other words, the sequence of integers determines a p-adic inte-
ger. Conversely, the partial sums of a p-adic integer determine a sequence of
integers satisfying (A.3).
Let™s use these ideas to show that ’1 is a square in the 5-adic integers. Let
x1 = 2, so
x2 ≡ ’1 (mod 5).
1

Suppose we have de¬ned xm such that

x2 ≡ ’1 (mod 5m ).
m

Let xm+1 = xm + b5m , where

’1 ’ x2
m
b≡ (mod 5).
mx
2·5 m

Note that x2 ≡ ’1 (mod 5m ) implies that the right side of this last congru-
m
ence is de¬ned mod 5. A quick calculation shows that

x2 m+1
m+1 ≡ ’1 (mod 5 ).

Since (A.3) is satis¬ed, there is a 5-adic integer x with x ≡ xm (mod 5m ) for
all m. Moreover,
x2 ≡ ’1 (mod 5m )
for all m. This implies that x2 = ’1.
In general, this procedure leads to the following very useful result.


THEOREM A.2 (Hensel™s Lemma)
Let f (X) be a polynomial with coe¬cients that are p-adic integers and suppose
x1 is an integer such that

f (x1 ) ≡ 0 (mod p).

If
f (x1 ) ≡ 0 (mod p),




© 2008 by Taylor & Francis Group, LLC
475
p-ADIC NUMBERS

then there exists a p-adic integer x with x ≡ x1 (mod p) and

f (x) = 0.

COROLLARY A.3
Let p be an odd prime and suppose b is a p-adic integer that is a nonzero
square mod p. Then b is the square of a p-adic integer.

The corollary can be proved by exactly the same method that was used to
prove that ’1 is a square in the 5-adic integers. The corollary can also be
deduced from the theorem as follows. De¬ne f (X) = X 2 ’ b and let x2 ≡ b
1
(mod p). Then f (x1 ) ≡ 0 (mod p) and

f (x1 ) = 2x1 ≡ 0 (mod p)

since p is odd and x1 ≡ 0 by assumption. Hensel™s Lemma shows that there
is a p-adic integer x with f (x) = 0. This means that x2 = b, as desired.
When p = 2, the corollary is not true. For example, 5 is a square mod 2 but
is not a square mod 8, hence is not a 2-adic square. However, the inductive
procedure used above yields the following:


PROPOSITION A.4
If b is a 2-adic integer such that b ≡ 1 (mod 8) then b is the square of a 2-adic
integer.




© 2008 by Taylor & Francis Group, LLC
© 2008 by Taylor & Francis Group, LLC
Appendix B
Groups


Basic de¬nitions
Since most of the groups in this book are additive abelian groups, we™ll
use additive notation for the group operations in this appendix. Therefore, a
group G has a binary operation + that is associative. There is an additive
identity that we™ll call 0 satisfying

0+g =g+0=g

for all g ∈ G. Each g ∈ G is assumed to have an additive inverse ’g satisfying

(’g) + g = g + (’g) = 0.

If n is a positive integer, we let

ng = g + g + · · · + g (n summands).

If n < 0, we let ng = ’(|n|g) = ’(g + · · · + g).
Almost all of the groups in this book are abelian, which means that g + h =
h + g for all g, h ∈ G.
If G is a ¬nite group, the order of G is the number of elements in G. The
order of an element g ∈ G is the smallest integer k > 0 such that kg = 0.
If k is the order of g, then

ig = jg ⇐’ i ≡ j (mod k).

The basic result about orders is the following.


THEOREM B.1 (Lagrange™s Theorem)
Let G be a ¬nite group.
1. Let H be a subgroup of G. Then the order of H divides the order of G.
2. Let g ∈ G. Then the order of g divides the order of G.


477

© 2008 by Taylor & Francis Group, LLC
478 APPENDIX B GROUPS

The ratio #G/#H is called the index of H in G. More generally, the index
of a (possibly in¬nite) subgroup H in a group G is the smallest number n of
elements such that we can write G as a union of translates of G by elements
gi ∈ G:
G = ∪n (gi + H) .
i=1

For example, Z = (0 + 3Z) ∪ (1 + 3Z) ∪ (2 + 3Z), so the index of 3Z in Z is 3.
A cyclic group is a group isomorphic to either Z or Zn for some n. These
groups have the property that they can be generated by one element. For
example, Z4 is generated by 1, and it is also generated by 3 since {0, 3, 3 +
3, 3 + 3 + 3} is all of Z4 . The following result says that the converse of
Lagrange™s theorem holds for ¬nite cyclic groups.


THEOREM B.2
Let G be a ¬nite cyclic group of order n. Let d > 0 divide n.

1. G has a unique subgroup of order d.

2. G has d elements of order dividing d, and G has φ(d) elements of order
exactly d (where φ(d) is Euler™s φ-function).

For example, Z6 contains the subgroup {0, 2, 4} of order 3. The elements
2, 4 ∈ Z6 have order 3.
The direct sum of two groups G1 and G2 is de¬ned to be the set of ordered
pairs formed from elements of G1 and G2 :

G1 • G2 = {(g1 , g2 ) | g1 ∈ G1 , g2 ∈ G2 }.

Ordered pairs can be added componentwise:

(g1 , g2 ) + (h1 , h2 ) = (g1 + h1 , g2 + h2 ).

This makes G1 •G2 into a group with (0, 0) as the identity element. A similar
de¬nition holds for the direct sum of more than two groups. We write Gr for
the direct sum of r copies of G. In particular, Zr denotes the set of r-tuples
of integers, which is a group under addition.




Structure theorems
Two groups, G1 and G2 , are said to be isomorphic if there exists a bijection
ψ : G1 ’ G2 such that ψ(gh) = ψ(g)ψ(h) for all g, h ∈ G1 (note that the
multiplication gh is in G1 while the multiplication ψ(g)ψ(h) takes place in
G2 ).




© 2008 by Taylor & Francis Group, LLC
479
STRUCTURE THEOREMS

THEOREM B.3
A ¬nite abelian group is isomorphic to a group of the form

Zn1 • Zn2 • · · · • Zns

with ni |ni+1 for i = 1, 2, . . . , s ’ 1. The integers ni are uniquely determined
by G.

An abelian group G is called ¬nitely generated if there is a ¬nite set
{g1 , g2 , . . . , gk } contained in G such that every element of G can be written
(not necessarily uniquely) in the form

m1 g1 + · · · + mk gk

with mi ∈ Z.


THEOREM B.4
A ¬nitely generated abelian group is isomorphic to a group of the form

Zr • Zn1 • Zn2 • · · · • Zns

with r ≥ 0 and with ni |ni+1 for i = 1, 2, . . . , s ’ 1. The integers r and ni are
uniquely determined by G.

The subgroup of G isomorphic to

Zn1 • Zn2 • · · · • Zns

is called the torsion subgroup of G. The integer r is called the rank of G.
This theorem can be used to prove the following.


THEOREM B.5
Let G1 ⊆ G2 ⊆ G3 be groups and assume that, for some integer r, both G1
and G2 are isomorphic to Zr . Then G2 is isomorphic to Zr .

For example, G1 = 12Z, G2 = 6Z, and G3 = Z, each of which is isomorphic
as a group to Z, satisfy the theorem. This theorem is used in the text when
G1 and G3 are lattices in C. Then G1 and G3 are isomorphic to Z2 . If
G1 ⊆ G2 ⊆ G3 , then G2 Z2 , so there exist ω1 , ω2 such that G2 = Zω1 +Zω2 .
Since G1 is a lattice, it contains two vectors that are linearly independent over
R. Since G1 ⊆ G2 , this implies that ω1 and ω2 are linearly independent over
R. Therefore, G2 is a lattice.




© 2008 by Taylor & Francis Group, LLC
480 APPENDIX B GROUPS




Homomorphisms
Let G1 , G2 be groups. A homomorphism from G1 to G2 is a map ψ :
G1 ’ G2 such that ψ(g + h) = ψ(g) + ψ(h) for all g, h ∈ G1 . In other words,
the map takes sums in G1 to the corresponding sums in G2 . The kernel of
ψ is
Ker ψ = {g ∈ G1 | ψ(g) = 0}.
The image of ψ is denoted ψ(G1 ), which is a subgroup of G2 . The main result
we need is the following.


THEOREM B.6
Assume G1 is a ¬nite group and ψ : G1 ’ G2 is a homomorphism. Then

#G1 = (#Ker ψ) (#ψ(G1 )) .

In fact, in terms of quotient groups, G1 /Ker ψ ψ(G1 ).




© 2008 by Taylor & Francis Group, LLC
Appendix C
Fields

Let K be a ¬eld. There is a ring homomorphism ψ : Z ’ K that sends
1 ∈ Z to 1 ∈ K. If ψ is injective, then we say that K has characteristic 0.
Otherwise, there is a smallest positive integer p such that ψ(p) = 0. In this
case, we say that K has characteristic p. If p factors as ab with 1 < a ¤
b < p, then ψ(a)ψ(b) = ψ(p) = 0, so ψ(a) = 0 or ψ(b) = 0, contradicting the
minimality of p. Therefore, p is prime.
When K has characteristic 0, the ¬eld Q of rational numbers is contained
in K. When K has characteristic p, the ¬eld Fp of integers mod p is contained
in K.
Let K and L be ¬elds with K ⊆ L. If ± ∈ L, we say that ± is algebraic
over K if there exists a nonconstant polynomial

f (X) = X n + an’1 X n’1 + · · · + a0

with a0 , . . . , an’1 ∈ K such that f (±) = 0. We say that L is an algebraic
over K, or that L is an algebraic extension of K, if every element of L is
algebraic over K. An algebraic closure of a ¬eld K is a ¬eld K containing
K such that

1. K is algebraic over K.

2. Every nonconstant polynomial g(X) with coe¬cients in K has a root in
K (this means that K is algebraically closed).

If g(X) has degree n and has a root ± ∈ K, then we can write g(X) =
(X ’ ±)g1 (X) with g1 (X) of degree n ’ 1. By induction, we see that g(X)
has exactly n roots (counting multiplicity) in K.
It can be shown that every ¬eld K has an algebraic closure, and that any two
algebraic closures of K are isomorphic. Throughout the book, we implicitly
assume that a particular algebraic closure of a ¬eld K has been chosen, and
we refer to it as the algebraic closure of K.
When K = Q, the algebraic closure Q is the set of complex numbers that
are algebraic over Q. When K = C, the algebraic closure is C itself, since
the fundamental theorem of algebra states that C is algebraically closed.


481

© 2008 by Taylor & Francis Group, LLC
482 APPENDIX C FIELDS




Finite ¬elds
Let p be a prime. The integers mod p form a ¬eld Fp with p elements. It can
be shown that the number of elements in a ¬nite ¬eld is a power of a prime,
and for each power pn of a prime p, there is a unique (up to isomorphism) ¬eld
with pn elements. (Note: The ring Zpn is not a ¬eld when n ≥ 2 since p does
not have a multiplicative inverse; in fact, p is a zero divisor since p · pn’1 ≡ 0
(mod pn ).) In this book, the ¬eld with pn elements is denoted Fpn . Another
notation that appears often in the literature is GF (pn ). It can be shown that

Fpm ⊆ Fpn ⇐’ m|n.

The algebraic closure of Fp can be shown to be

Fp = Fpn .
n≥1



THEOREM C.1
Let Fp be the algebraic closure of Fp and let q = pn . Then

Fq = {± ∈ Fp | ±q = ±}.


PROOF The group F— of nonzero elements of Fq forms a group of order
q
q’1
= 1 when 0 = ± ∈ Fq . Therefore, ±q = ± for all ± ∈ Fq .
q ’ 1, so ±
Recall that a polynomial g(X) has multiple roots if and only if g(X) and
g (X) have a common root. Since

d
(X q ’ X) = qX q’1 ’ 1 = ’1
dX
(since q = pn = 0 in Fp ), the polynomial X q ’ X has no multiple roots.
Therefore, there are q distinct ± ∈ Fp such that ±q = ±.
Since both sets in the statement of the theorem have q elements and one is
contained in the other, they are equal.

De¬ne the q-th power Frobenius automorphism φq of Fq by the formula

φq (x) = xq for all x ∈ Fq .


PROPOSITION C.2
Let q be a power of the prime p.

1. Fq = Fp .




© 2008 by Taylor & Francis Group, LLC
483
FINITE FIELDS

2. φq is an automorphism of Fq . In particular,
φq (x + y) = φq (x) + φq (y), φq (xy) = φq (x)φq (y)
for all x, y ∈ Fq .
3. Let ± ∈ Fq . Then
φn (±) = ±.
± ∈ Fqn ⇐’ q


PROOF Part (1) is a special case of a more general fact: If K ⊆ L and
every element of L is algebraic over K, then L = K. This can be proved
as follows. If ± is algebraic over L and L is algebraic over K, then a basic
property of algebraicity is that ± is then algebraic over K. Therefore, L is
algebraic over K and is algebraically closed. Therefore, it is an algebraic
closure of K.
Part (3) is just a restatement of Theorem C.1, with q n in place of q.
We now prove part (2). If 1 ¤ j ¤ p ’ 1, the binomial coe¬cient p has a
j
factor of p in its numerator that is not canceled by the denominator, so
p
≡ 0 (mod p).
j
Therefore,
p p’1 p p’2 2
(x + y)p = xp + x y + · · · + yp
x y+
1 2
= xp + y p
since we are working in characteristic p. An easy induction yields that
n n n
(x + y)p = xp + y p
for all x, y ∈ Fp . This implies that φq (x + y) = φq (x) + φq (y). The fact
that φq (xy) = φq (x)φq (y) is clear. This proves that φq is a homomorphism
of ¬elds. Since a homomorphism of ¬elds is automatically injective (see the
discussion preceding Proposition C.5), it remains to prove that φq is surjective.
If ± ∈ Fp , then ± ∈ Fqn for some n, so φn (±) = ±. Therefore, ± is in the
q
image of φq , so φq is surjective. Therefore, φq is an automorphism.

In Appendix A, it was pointed out that F— = Z— is a cyclic group, gener-
p p
ated by a primitive root. More generally, it can be shown that F— is a cyclic
q
group. A useful consequence is the following.


PROPOSITION C.3
Let m be a positive integer with p m and let µm be the group of mth roots of
unity. Then
µm ⊆ F— ⇐’ m|q ’ 1.
q




© 2008 by Taylor & Francis Group, LLC
484 APPENDIX C FIELDS

PROOF By Lagrange™s theorem (see Appendix B), if µm ⊆ F— , then q

m|q ’ 1. Conversely, suppose m|q ’ 1. Since Fq is cyclic of order q ’ 1, it
has a subgroup of order m (see Appendix B). By Lagrange™s theorem, the
elements of this subgroup must satisfy xm = 1, hence they must be the m
elements of µm .

Let Fq ⊆ Fqn be ¬nite ¬elds. We can regard Fqn as a vector space of
dimension n over Fq . This means that there is a basis {β1 , . . . , βn } of elements
of Fqn such that every element of Fqn has a unique expression of the form

a1 β1 + · · · + an βn

with a1 , . . . , an ∈ Fq . The next result says that it is possible to choose a basis
of a particularly nice form, sometimes called a normal basis.


PROPOSITION C.4
There exists β ∈ Fqn such that

{β, φq (β), . . . , φn’1 (β)}
q

is a basis of Fqn as a vector space over Fq .

An advantage of a normal basis is that the qth power map becomes a shift
operator on the coordinates: Let

x = a1 β + a2 φq (β) + · · · + an φn’1 (β),
q

with ai ∈ Fq . Then aq = ai and φn (β) = β, so
q
i

xq = a1 β q + a2 φq (β q ) + · · · + an φn’1 (β q )
q

= an φn (β) + a1 φq (β) + · · · + an’1 φn’1 (β)
q q

= an β + a1 φq (β) + · · · + an’1 φn’1 (β).
q

Therefore, if x has coordinates (a1 , . . . , an ) with respect to the normal basis,
then xq has coordinates (an , a1 , . . . , an’1 ). Therefore, the computation of
qth powers is very fast and requires no calculation in Fqn . This has great
computational advantages.




Embeddings and automorphisms
Let K be a ¬eld of characteristic 0, so Q ⊆ K. An element ± ∈ K is
called transcendental if it is not the root of any nonzero polynomial with




© 2008 by Taylor & Francis Group, LLC
485
EMBEDDINGS AND AUTOMORPHISMS

rational coe¬cients, that is, if it is not algebraic over Q. A set of elements S =
{±i } ⊆ K (with i running through some (possibly in¬nite) index set I) is called
algebraically dependent if there are n distinct elements ±1 , . . . , ±n of S, for
some n ≥ 1, and a nonzero polynomial f (X1 , . . . , Xn ) with rational coe¬cients
such that f (±1 , . . . , ±n ) = 0. The set S is called algebraically independent
if it is not algebraically dependent. This means that there is no polynomial
relation among the elements of S. A maximal algebraically independent subset
of K is called a transcendence basis of K. The transcendence degree
of K over Q is the cardinality of a transcendence basis (the cardinality is
independent of the choice of transcendence basis). If every element of K
is algebraic over Q, then the transcendence degree is 0. The transcendence
degree of C over Q is in¬nite, in fact, uncountably in¬nite.
Let K be a ¬eld of characteristic 0, and choose a transcendence basis S. Let
F be the ¬eld generated by Q and the elements of S. The maximality of S
implies that every element of K is algebraic over F . Therefore, K can be ob-
tained by starting with Q, adjoining algebraically independent transcendental
elements, then making an algebraic extension.
Let K and L be ¬elds and let f : K ’ L be a homomorphism of ¬elds. We
always assume f maps 1 ∈ K to 1 ∈ L. Then f is injective. One way to see
this is to note that if 0 = x ∈ K, then 1 = f (x)f (x’1 ) = f (x)f (x)’1 ; since
f (x) has a multiplicative inverse, it cannot be 0.
The following result is very useful. It is proved using Zorn™s Lemma (see
[71]).

PROPOSITION C.5
Let K and L be ¬elds. Assume that L is algebraically closed and that there
is a ¬eld homomorphism
f : K ’’ L.
˜
˜
Then there is a homomorphism f : K ’ L such that f restricted to K is f .

Proposition C.5 has the following nice consequence.


COROLLARY C.6
Let K be a ¬eld of characteristic 0. Assume that K has ¬nite transcendence
degree over Q. Then there is a homomorphism K ’ C. Therefore, K can be
regarded as a sub¬eld of C.


PROOF Choose a transcendence basis S = {±1 , . . . , ±n } of K and let F be
the ¬eld generated by Q and S. Since C has uncountable transcendence degree
over Q, we can choose n algebraically independent elements „1 , . . . , „n ∈ C.
De¬ne f : F ’ C by making f the identity map on Q and setting f (±j ) = „j
˜
for all j. The proposition says that f can be extended to f : F ’ C. Since
˜
K is an algebraic extension of F , we have K ⊆ F . Restricting f to K yields




© 2008 by Taylor & Francis Group, LLC
486 APPENDIX C FIELDS

the desired homomorphism from K ’ C. Since a homomorphism of ¬elds is
injective, K is isomorphic to its image under this homomorphism. Therefore,
K is isomorphic to a sub¬eld of C.

The proposition also holds, with a similar proof, if the transcendence degree
of K is at most the cardinality of the real numbers, which is the cardinality
of a transcendence basis of C.
If ± ∈ C is algebraic over Q, then f (±) = 0 for some nonzero polynomial
with rational coe¬cients. Let Aut(C) be the set of ¬eld automorphisms of
C and let σ ∈ Aut(C). Then σ(1) = 1, from which it follows that σ is the
identity on Q. Therefore,

0 = σ(f (±)) = f (σ(±)),

so σ(±) is one of the ¬nitely many roots of f (X). The next result gives a
converse to this fact.


PROPOSITION C.7
Let ± ∈ C. If the set
{σ(±) | σ ∈ Aut(C)},
where σ runs through all automorphisms of C, is ¬nite, then ± is algebraic
over Q.


PROOF Suppose ± is transcendental. There is a transcendence basis S of
C with ± ∈ S. Then C is algebraic over the ¬eld F generated by Q and S.
The map

σ : F ’’ F
± ’’ ± + 1
β ’’ β when β ∈ S, β = ±

de¬nes an automorphism of F . By Proposition C.5, σ can be extended to
a map σ : C ’ C. We want to show that σ is an automorphism, which
˜ ˜
means that we must show that σ is surjective. Let y ∈ C. Since y is algebraic
˜
over F , there is a nonzero polynomial g(X) with coe¬cients in F such that
’1
g(y) = 0. Let g σ denote the result of applying σ ’1 to all of the coe¬cients
of g (note that we know σ ’1 exists on F because we already know that σ is
’1
an automorphism of F ). For any root r of g σ , we have
’1
0 = σ gσ
˜ (r) = g(˜ (r)).
σ

’1
Therefore, σ maps the roots of g σ to roots of g. Since the two polynomials
˜
have the same number of roots, σ gives a bijection between the two sets of
˜




© 2008 by Taylor & Francis Group, LLC
487
EMBEDDINGS AND AUTOMORPHISMS

roots. In particular, σ (r) = y for some r. Therefore, y is in the image of σ .
˜ ˜
This proves that σ is surjective, so σ is an automorphism of C.
˜ ˜
Since
σ j (±) = ± + j,
˜
the set of images of ± under automorphisms of C is in¬nite, in contradiction
to our assumption. Therefore, ± cannot be transcendental, hence must be
algebraic.

REMARK C.8 In Proposition C.7, the assumption that the set is ¬nite
can be changed to assuming that the set is countable, with essentially the
same proof. Namely, if ± is transcendental, then, for any γ ∈ S, there is an
automorphism σ satisfying σ(±) = ± + γ. The fact that S is uncountable
yields the result.




© 2008 by Taylor & Francis Group, LLC
© 2008 by Taylor & Francis Group, LLC
Appendix D
Computer Packages

There are several computer algebra packages available that do calculations
on elliptic curves. In this appendix, we give a brief introduction to three of
the major packages. Rather than give explanations of the structure of these
packages, we simply include some examples of some computations that can
be performed with them. The reader should consult the documentation that
is available online or with the packages to see numerous other possibilities.




D.1 Pari
Pari/GP is a free computer algebra system for number theory calculations.
It can be downloaded from http://pari.math.u-bordeaux.fr/.
Here is a transcript of a session, with commentary.

GP/PARI CALCULATOR Version 2.3.0 (released)
i686 running linux (ix86 kernel) 32-bit version
compiled: Aug 16 2007, gcc-3.4.4 20050721 (Red Hat 3.4.4-2)
(readline v4.3 enabled [was v5.0 in Configure], extended help
available)
Copyright (C) 2000-2006 The PARI Group

PARI/GP is free software, covered by the GNU General Public
License, and comes WITHOUT ANY WARRANTY WHATSOEVER.
Type ? for help, \q to quit. Type ?12 for how to get moral
(and possibly technical) support.
parisize = 4000000, primelimit = 500000
First, we need to enter and initialize an elliptic curve. Let [a1 , a2 , a3 , a4 , a6 ]
be the coe¬cients for the curve in generalized Weierstrass form. Start with
the curve of Example 9.3: E1 : y 2 = x3 ’ 58347x + 3954150.
? e1=ellinit([0,0,0,-58347,3954150])
%1 = [0, 0, 0, -58347, 3954150, 0, -116694, 15816600,


489

© 2008 by Taylor & Francis Group, LLC
490 APPENDIX D COMPUTER PACKAGES

-3404372409, 2800656, -3416385600, 5958184124547072,
10091699281/2737152, [195.1547871847901607239497645,
75.00000000000000000000000000, -270.1547871847901607239497645],
0.1986024692687475355260042188, 0.1567132675477145982613047883*I,
-6.855899811988574944063544705, -21.22835194662770142565252843*I,
0.03112364190214999895971387115]
The output contains several parameters for the curve (type ?ellinit to
see an explanation). For example, the periods ω1 = i0.156713 . . . and ω2 =
0.198602 . . . are entries. The j-invariant is the 13th entry:
? e1[13]
%2 = 10091699281/2737152
Here is the curve E2 : y 2 = x3 + 73:
? e2=ellinit([0,0,0,0,73])
%3 = [0, 0, 0, 0, 73, 0, 0, 292, 0, 0, -63072, -2302128, 0,
[-4.179339196381231892056376349, 2.089669598190615946028188174
+ 3.619413915098187674530455654*I, 2.089669598190615946028188174
-3.619413915098187674530455654*I], 2.057651708004923756251055780,
-1.028825854002461878125527890+0.5939928837575679811100134634*I,
-2.644469941892436553395125300, 1.322234970946218276697562650
-2.290178149223208371431388983*I, 1.222230471806529890431614914]
We can add the points (2, 9) and (3, 10), which lie on the curve:
? elladd(e2,[2,9],[3,10])
%4 = [-4, -3]
We can compute the 3rd multiple of (2, 9):
? ellpow(e2,[2,9],3)
%5 = [5111/625, -389016/15625]
The torsion subgroup of the Mordell-Weil group can be computed:
? elltors(e1)
%6 = [10, [10], [[3, 1944]]]
? elltors(e2)
%7 = [1, [], []]
The ¬rst output says that the torsion subgroup of E1 (Q) has order 10, it
is cyclic of order 10, and it is generated by the point (3, 1944). The second
output says that the torsion subgroup of E2 (Q) is trivial.
The number of points on an elliptic curve mod a prime p has the form
p + 1 ’ ap . The value of a13 for E1 is computed as follows:
? ellap(e1,13)
%8 = 4
Therefore, there are 13 + 1 ’ 4 = 10 points on E1 mod 13.




© 2008 by Taylor & Francis Group, LLC
491
SECTION D.1 PARI

We can also compute with curves mod p. Let™s consider E3 : y 2 = x3 +
10x + 5 (mod 13) (this is the reduction of E1 mod 13):
? e3=ellinit([0,0,0,Mod(10,13),Mod(5,13)])
%9 = [0, 0, 0, Mod(10, 13), Mod(5, 13), 0, Mod(7, 13),
Mod(7, 13), Mod(4, 13), Mod(1, 13), Mod(9, 13), Mod(2, 13),
Mod(7, 13), 0, 0, 0, 0, 0, 0]
Multiples of points can be computed as before:
? ellpow(e3,[Mod(3,13),Mod(7,13)],10)
%10 = [0]
? ellpow(e3,[Mod(3,13),Mod(7,13)],5)
%11 = [Mod(10, 13), Mod(0, 13)]
The ¬rst output means that the 10th multiple of the point is ∞.
The height pairing can be computed. For example, on E2 the pairing
(2, 9), (3, 10) from Example 8.11 is computed as follows:
? ellbil(e2,[2,9],[3,10])
%12 = -0.9770434128038324411625933747
Pari works with the complex functions associated to an elliptic curve. For

example, the value of j((1 + ’171)/2) (see the beginning of Section 10.4) is
computed as follows:
? ellj((1+sqrt(-171))/2)
%13 = -694282057876536664.0122886865 + 0.0000000003565219231*I
We know the value should be real. To increase the precision to 60 digits,
type:
? \p 60
realprecision = 67 significant digits (60 digits displayed)
Now, retype the previous command:
? ellj((1+sqrt(-171))/2)
%14 = -694282057876536664.0122886867083074260443674536412446626
29851 - 7.05609883 E-49*I
The imaginary part of the answer is less than 10’48 .
To ¬nd other functions that are available, type ?. To ¬nd the functions
that relate to elliptic curves, type ?5. To ¬nd how to use a command, for
example elladd, type
?elladd
elladd(e,z1,z2): sum of the points z1 and z2 on elliptic
curve e.
To quit, type
? \q
Goodbye!




© 2008 by Taylor & Francis Group, LLC
492 APPENDIX D COMPUTER PACKAGES




D.2 Magma
Magma is a large computer algebra package. It requires a license to use.
It is available on some institutional computers. For general information, see
http://magma.maths.usyd.edu.au/magma/.
The following is the transcript of a session, with commentary.
The session starts:
Magma V2.11-14 Thu Nov 1 2007 15:48:04 [Seed = 3635786414]
Type ? for help. Type <Ctrl>-D to quit.
Let™s enter the elliptic curve E1 : y 2 = x3 ’ 58447x + 3954150 of Example
9.3. The vector represents the coe¬cients [a1 , a2 , a3 , a4 , a6 ] in generalized
Weierstrass form. Unless otherwise speci¬ed, the curve is over the rational
numbers.
> E1:= EllipticCurve( [ 0, 0, 0, -58347, 3954150 ]);
Note that the line needs to end with a semicolon. To ¬nd out what E1 is:
> E1;
Elliptic Curve defined by yˆ2 = xˆ3 - 58347*x + 3954150 over
Rational Field
Let™s also de¬ne E2 : y 2 = x3 + 73. Here we use the shortened form of the
coe¬cient vector [a4 , a6 ] corresponding to (nongeneralized) Weierstrass form.
> E2:= EllipticCurve( [ 0, 73 ]);
Let™s add the points (2, 9) and (3, 10) on E2 . The notation E2![2,9] spec-
i¬es that [2, 9] lives on E2 , rather than in some other set.
> E2![2,9] + E2![3, 10];
(-4 : -3 : 1)
Note that the answer is in projective coordinates. We could have done the
computation with one or both points in projective coordinates. For example:
> E2![2,9] + E2![3, 10, 1];
(-4 : -3 : 1)
The identity element of E2 is
> E2!0;
(0 : 1 : 0)
We can also de¬ne a point using :=
> S:= E2![2,9] + E2![3, 10];
To ¬nd out what S is:
> S;
(-4 : -3 : 1)
The computer remembers that S lies on E2 , so we can add it to another
point on E2 :




© 2008 by Taylor & Francis Group, LLC
493
SECTION D.2 MAGMA

> S + E2![2, 9];
(6 : -17 : 1)
To ¬nd the 3rd multiple of the point (2, 9) on E2 :
> 3*E2![2,9];
(5111/625 : -389016/15625 : 1)
To ¬nd the torsion subgroup of E1 (Q):
> TorsionSubgroup(E1);
Abelian Group isomorphic to Z/10
Defined on 1 generator
Relations:
10*$.1 = 0
Note that we obtained only an abstract group, not the points. To get the
points, we de¬ne a group G and an isomorphism f from G to the set of points:

> G, f:= TorsionSubgroup(E1);
To obtain the ¬rst element of G, type:
> f(G.1);
(3 : 1944 : 1)
This is a torsion point in E1 (Q).
Let™s reduce E1 mod 13. De¬ne F to be the ¬eld with 13 elements and E3
to be E1 mod 13:
> F:= GF(13);
> E3:= ChangeRing( E1, F );
> E3; Elliptic Curve defined by yˆ2 = xˆ3 +10*x + 5 over GF(13)
The last command was not needed. It simply identi¬ed the nature of E3 .
We also could have de¬ned a curve over F13 . The command F!10 puts 10
into F13 , which forces everything else, for example 5, to be in F13 :
> E4:= EllipticCurve( [F!10, 5]);
> E4;
Elliptic Curve defined by yˆ2 = xˆ3 +10*x + 5 over GF(13)
> E3 eq E4;
true
The last command asked whether E3 is the same as E4 . The answer was
yes.
We can ¬nd out how many points there are in E3 (F13 ), or we can list all
the points:
> #E3;
10
> Points(E3);
{@ (0 : 1 : 0), (1 : 4 : 1), (1 : 9 : 1), (3 : 6 : 1),
(3 : 7 : 1), (8 : 5 : 1), (8 : 8 : 1), (10 : 0 : 1),




© 2008 by Taylor & Francis Group, LLC
494 APPENDIX D COMPUTER PACKAGES

(11 : 4: 1), (11 : 9: 1) @}
The @™s in the last output speci¬es that the entries are a set indexed by
positive integers.
Let™s compute the Weil pairing e3 ((0, 3), (5, 1)) on the curve E5 : y 2 = x2 +2
over F7 , as in Example 11.5.
> E5:= EllipticCurve([0, GF(7)!2]);
> WeilPairing( E5![0,3], E5![5,1], 3);
4
The answer is 4, which is a cube root of unity in F7 . Note that this is the
inverse of the Weil pairing used elsewhere in this book (cf. Remark 11.11).
We can compute the Mordell-Weil group E2 (Q):
> MordellWeilGroup(E2);
Abelian Group isomorphic to Z + Z
Defined on 2 generators (free)
> Generators(E2);
[ (2 : 9 : 1), (-4 : 3 : 1) ]
To ¬nd a command that computes, for example, Mordell-Weil groups, type
?MordellWeil or ?Mordell to get an example or a list of examples.
To quit Magma, type
<Ctrl>D
For much more on Magma, go to
http://magma.maths.usyd.edu.au/magma/htmlhelp/MAGMA.htm
For elliptic curves, click on the Arithmetic Geometry link.




D.3 SAGE
Sage is an open source computer algebra package that can be downloaded
for free from www.sagemath.org/. For general information, see the web site,
which also contains a tutorial and documentation.
The following is the transcript of a session, with commentary.
The session starts:
Linux sage 2.6.17-12-386 #2 Sun Sep 23 22:54:19 UTC 2007 i686
The programs included with the Ubuntu system are free software;
the exact distribution terms for each program are described in
the individual files in /usr/share/doc/*/copyright.
Ubuntu comes with ABSOLUTELY NO WARRANTY, to the extent
permitted by applicable law.

| SAGE Version 2.8.8.1, Release Date: 2007-10-21 |




© 2008 by Taylor & Francis Group, LLC
495
SECTION D.3 SAGE

| Type notebook() for the GUI, and license() for information. |

Let™s enter the elliptic curve E1 : y 2 = x3 ’ 58447x + 3954150 of Example
9.3. The vector represents the coe¬cients [a1 , a2 , a3 , a4 , a6 ] in generalized
Weierstrass form. Unless otherwise speci¬ed, the curve is over the rational
numbers.
sage: E1 = EllipticCurve([ 0, 0, 0, -58347, 3954150 ])
To ¬nd out what E1 is:
sage: E1
Elliptic Curve defined by yˆ2 = xˆ3 - 58347*x + 3954150 over
Rational Field
Let™s also de¬ne E2 : y 2 = x3 + 73. Here we use the shortened form of the
coe¬cient vector [a4 , a6 ] corresponding to (nongeneralized) Weierstrass form.
sage: E2 = EllipticCurve([ 0, 73 ]);
Let™s add the points (2, 9) and (3, 10) on E2 :
sage: E2([2,9]) + E2([3, 10])
(-4 : -3 : 1)
Note that the answer is in projective coordinates. We could have done the
computation with one or both points in projective coordinates. For example:
sage: E2([2,9]) + E2([3, 10, 1])
(-4 : -3 : 1)
The identity element of E2 is
sage: E2(0)
(0 : 1 : 0)
We can also de¬ne a point:
sage: S = E2([2,9]) + E2([3, 10])
To ¬nd out what S is:
sage: S
(-4 : -3 : 1)
The computer remembers that S lies on E2 , so we can add it to another
point on E2 :
sage: S + E2([2, 9])
(6 : -17 : 1)
To ¬nd the 3rd multiple of the point (2, 9) on E2 :
sage: 3*E2([2,9])
(5111/625 : -389016/15625 : 1)
To ¬nd the torsion subgroup of E1 (Q):
sage: E1.torsion subgroup()
Torsion Subgroup isomorphic to Multiplicative Abelian Group




© 2008 by Taylor & Francis Group, LLC
496 APPENDIX D COMPUTER PACKAGES

isomorphic to C10 associated to the Elliptic Curve defined by
y2 = x3 - 58347*x + 3954150 over Rational Field
C10 denotes the cyclic group of order 10. To get a generator:
sage: E1.torsion subgroup().gen()
(3 : 1944 : 1)
The number of points on an elliptic curve mod a prime p has the form
p + 1 ’ ap . The value of a13 for E1 is computed as follows:
sage: E1.ap(13)
4
Therefore, there are 13 + 1 ’ 4 = 10 points on E1 mod 13.
Let™s reduce E1 mod 13:
sage: E3 = E2.change ring(GF(13))
sage: E3
Elliptic Curve defined by yˆ2 = xˆ3 +10*x + 5
over Finite Field of size 13
The last command was not needed. It simply identi¬ed the nature of E3 .
We also could have de¬ned a curve over F13 .
sage: E4 = EllipticCurve(GF(13), [10, 5])
sage: E4
Elliptic Curve defined by yˆ2 = xˆ3 +10*x + 5
over Finite Field of size 13
sage: E3 is E4
True
The last command asked whether E3 is the same as E4 . The answer was
yes.
We can ¬nd out how many points there are in E3 (F13 ), or we can list all
the points:
sage: E3.cardinality()
10
sage: E3.points()
[(0 : 1 : 0),
(11 : 4 : 1),
(8 : 5 : 1),
(1 : 4 : 1),
(10 : 0 : 1),
(1 : 9 : 1),
(3 : 6 : 1),
(8 : 8 : 1),
(11 : 9 : 1),
(3 : 7 : 1)]
Consider the curve E5 : y 2 = x3 ’ 1 over F229 , as in Example 4.10. We can
compute its group structure:




© 2008 by Taylor & Francis Group, LLC
497
SECTION D.3 SAGE

sage: EllipticCurve(GF(229),[0,-1]).abelian group()
(Multiplicative Abelian Group isomorphic to C42 x C6,
((62 : 25 : 1), (113 : 14 : 1)))
Therefore, E5 (F229 ) Z42 • Z6 , and it has the listed generators.
Let™s compute the rank and generators of the Mordell-Weil group E2 (Q):
sage: E2.rank()
2
sage: E2.gens()
[(-4 : 3 : 1),(2: 9 : 1)]
The generators are the generators of the nontorsion part. The command
does not yield generators of the torsion subgroup. For these, use the command
E.torsion subgroup().gen() used previously.
To ¬nd the periods ω1 and ω2 of E1 :
sage: E1.period lattice.0
0.1986024692687475355260042188...
sage: E1.period lattice.1
0.1567132675477145982613047883...*I
The j-invariant of E1 is
sage: E1.j invariant()
10091699281/2737152
To ¬nd a list of commands that start with a given string of letters, type
those letters and then press the “Tab” key:
sage: Ell (˜Tab™)
Ellipsis EllipticCurve from c4c6
EllipticCurve EllipticCurve from cubic
To ¬nd out about the command EllipticCurve, type
sage: EllipticCurve?
The output is a description with some examples.
For more on SAGE, go to http://www.sagemath.org.




© 2008 by Taylor & Francis Group, LLC
© 2008 by Taylor & Francis Group, LLC