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