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.

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

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,

(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
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.
в€’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

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

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
).

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.
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
%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:
%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, , [[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 = 
? 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
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
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
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