... Gauss^1.1

An often told story (the exact details of which depend on the source) of Gauss as a boy: As a 10 year old student in school, Gauss astonished his teacher who, wanting a break, told his class to add up all the numbers from 1 to 100. Gauss figured out the answer in a matter of seconds. He had noticed that by pairing $1$ and $100$, $2$ and $99$, ..., $50$ and $51$, all the paired numbers added to $101$ and that there were $50$ such pairs, so the answer was $5050$.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... wins^1.2

This is a two-person game in the sense of §2.9 below.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... multiplication^1.3

This means that (i) if $a,b\in I$ then $a+b\in I$ and (ii) if $a,b\in I$ then $a\cdot b\in I$.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... here^1.4

In fact, a ``polynomial time'' primality test has recently (August 2002) been announced. This would be a very important result. However, at the time of this writing, it has not yet passed the refereeing process for publication.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... Fermat^1.5

Fermat (1601-1665) was by profession a lawyer and judge in Toulouse, France. There were no real employment opportunities in mathematics at the time (at least not like there are now). Though perhaps most famous as a number theorist, he also worked on the foundations of calculus, and he is widely regarded as the best French mathematician of that century and one of the greatest number theorists of all time.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... primitive^1.6

See Definition 2.6.5 in the next chapter.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... prime^1.7

However, it has been shown by Pomerance, Granville, and Alford that there are infinitely many composite integers which are Fermat pseudoprimes to all bases $a$.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...RSA^1.8

It has recently been declassified that a very similar idea was developed earlier by Cliff Cocks, a British cryptographer, though the Cocks paper was classified until 1997 [E].

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... sequences^1.9

Though we shall not prove it here, it is known that each real number $x$ has a continued fraction expansion and that the $n^{th}$ convergents provide, in some sense, the best rational approximation to $x$. See chapter 10 of [HW] for example.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... computer^1.10

Assuming the converse to the Lucas-Perrin Lemma holds, the ``prime candidate'' would definitely be a prime

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... computer^1.11

Assuming the converse to the Lucas-Perrin Lemma holds, the ``prime candidate'' would definitely be a prime

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... variable^2.1

Polynomials in several variables can be treated similarly and will also be discussed below.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...ring ^2.2

More precisely, such an algebraic structure is called a ``commutative ring with unit''. All ``rings'' in this book shall be ``commutative rings with unit''.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...2.2^2.3

The following joke (told to one of us by Bill Wardlaw, illustrates this definition: Two young mathematics students, Alice and Bob, were out enjoying a picnic on a nice day in a field of clovers. They were not yet engaged to be married, so Alice put Bob's amorous advances on check when she said ``Not until I have a ring!'' Bob, knowing Alice was taking an abstract algebra course, countered ``But we're in a field. Can't we take this field as our ring?''

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... algebra^2.4

For those who have not had a course in linear algebra, vectors spaces are defined in the next chapter.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... ring^2.5

Recall that a ring similar to a field except that a non-zero element need not have an inverse.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... way^2.6

With these binary operations on $F[x]$, it turns out that $F[x]$ is a ring in the sense of the definition above.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... coefficients^2.7

Alternatively, one could think of polynomials $p(x)$ over a finite field $F$ as really being functions on an ``algebraic closure'' $\overline{F}$ (a certain infinite field containing $F$) which has been restricted to $F$

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... coefficients^2.8

This condition says that $I$ is an ideal in $F[x]$.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... function^2.9

Such a function is called a ``relation on $S$''.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... ordering^2.10

Some people also call this a linear ordering.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... well-ordering^2.11

This means every non-empty subset has a smallest element with respect to $\leq$.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... codes^3.1

In general, much more is known about $A_q(n,d)$ for ``very small'' and ``very large'' values of $d$ than for ``arbitrary values'' of $d$. See [MS] for further information.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...N^3.2

Some errors in this paper are corrected in [Mont].

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... example^3.3

A minor point: here $Hv$ must be typed in as $v*H^t$ since MAGMA (in the Australian tradition?) has matrices acting on the right.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... 2-cycles^4.1

There is an analogous result valid only for even permutations: each even permutation may be written as a product of (not necessarily disjoint) $3$-cycles.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... table^5.1

This terminology is inappropriate when $G$ is given additively; in that case, it is called the addition table.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... determinant^5.2

Matrices and determinants are defined more formally later in the chapter on groups.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... plane^5.3

If we regard $R$ as a figure in $3$-space centered above the origin and let $G$ denote the set of all linear transformations of $3$-space then we obtain a slightly larger group in some cases [NST].

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... group^5.4

Ans: 105, 6, 4, resp.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... group^5.5

Ans: 105, 6, 4, resp.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... rows^6.1

The $i^{th}$ row of $H$ corresponds to the $i^{th}$ parity check equation defining $C$, hence the name ``check vertex''.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... non-free^7.1

Not free but not for profit either. The cost of the license is put into further development of the package.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... constant^7.2

Declare both $a,T$ as variables.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.