# Math 75 Notes

** Math 75 Notes **

## 1 Euclid's algorithm and Z/(p)

We start at a place that might seem a bit far a field:
Euclid's algorithm from elementary number

theory for finding the greatest common divisor of two integers. Take the example
of the integers

91 and 143. We start Euclid's algorithm by taking the smaller of the numbers,
91, into the

larger; this goes in once and leaves a remainder of 52. We then take the
remainder, 52, into the

last divisor, 91. This goes in once, and we find a new remainder of 39. We keep
this process

up until one of these divisions works out without any remainder. According to
Euclid, the last

nonzero remainder (13 in this case) is the gcd:

143 = 91 · 1 + 52

91 = 52 · 1 + 39

52 = 39 · 1 + 13

39 = 13 · 3 + 0:

For another example we could take the numbers 7 and 17:

17 = 7 · 2 + 3

7 = 3 · 2 + 1

3 = 1 · 3 + 0;

so that in this case Euclid's algorithm tells us that 7
and 17 are relatively prime: their only

common positive divisor is the number 1.

It is tempting to suppose that Euclid's algorithm was
wasted on our last example. Indeed,

17 is a number which is immediately recognizable as a prime, so that it is
obvious it has no

factors in common with the smaller integer 7. But our e ort is not in vain!
Indeed, for our

purposes it is not the final answer of Euclid's algorithm (which we could have
predicted was 1

immediately) that is of interest, but the intermediate steps to reach that
outcome which are of

most interest.

These computations allow us to express 1 as a linear
combination of 17 and 7. We start by

writing

3 = 17 - 7 · 2,

which comes from the first of our Euclidean steps above.
Thus we have 3 as a linear combination

of 7 and 17. Next we write

1 = 7 - 3 · 2;

which is the result of transposing the second Euclidean
step above. This gives 1 as a combination

of 7 and 3. But we determined that 3 = 17 · 1 + 7(-2),
and so

1 = 7 · 1 - (17 · 1 + 7(-2))2 = 7 · 5 + 17(-2):

And now if we look at this equation in the system Z =(17), where 17 = 0, we find that

1 = 7 · 5.

So our computation with Euclid's algorithm has earned its
keep: it allowed us to construct an

inverse of 7 modulo 17.

More generally, Euclid's algorithm gives one a
constructive proof of the following important

result:

**Theorem 1. **Let a; b be integers, not both zero, and
let d be the greatest common divisor of a

and b. Then there are integers x and y with

ax + by = d:

In particular, if a and b are relatively prime, then one can solve the equation

ax + by = 1:

This allows us to settle one of our outstanding debts. We
can now prove the following result,

mentioned in the introductory lecture:

**Theorem 2.** Let p be a prime. Then Z/(p) is a eld.

The proof is now easy. We already know everything we need
to know about F = Z/(p),

except for the existence of multiplicative inverses for everything in F \ {0}.
But Z/(p) =

{0, 1,…, p - 1}, and so F \ {0} = {1, 2,…, p - 1}. Each of a = 1, 2, 3,…, p - 1 are relatively

prime to p, so that we can solve

ax + py = 1:

Reading this equation in Z/(p), we see that ax = 1, so that a has an inverse modulo p. Done!

It is worth emphasizing that the way we have proved this
result not only shows the existence

of inverses but gives an algorithm for computing them.

**Example 1.** Let p = 101 and a = 11. Find a^{-1} in
Z/(p).

Solution . We begin by performing Euclid's algorithm on the integers 11 and 101:

101 = 11 · 9 + 2

11 = 2 · 5 + 1

2 = 1 · 2 + 0:

Now we solve for 1 as a linear combination of 11 and 101:

2 = 101 + 11 · (-9)

1 = 11 + 2 · (-5)

= 11 + (101 + 11 · (-9)) · (-5)

= 11 · 46 + 101 · (-5):

Reading this last equation in Z/(101), we see 1 = 11 46. So 46 is the inverse of 11.

## 2 Constructing new fields from old

The insight that Z/(p) is a field is from the viewpoint of generalization a rather
fundamental

one. Cast in broad terms , we started with a system Z (not itself a field) and
created a field

by supplementing the arithmetic of Z with a new equation 'p = 0' for a prime p.
In order to

understand all finite fields, we will use a similar construction, but with systems
other than Z

as our starting points. We now introduce these systems.

Let F be a field. We de fine the univariate polynomials over F in the indeterminate
x as

the set of expressions of the form

where all the a_{i} belong to F. The degree of a polynomial is the highest power of
x that appears

with a nonzero coefficient ; for example, over R, the polynomial 3x^{2} + 1 has degree
2 and the

constant polynomial 1 = 1x^{0} has degree 0. The polynomial 0 (corresponding to
choosing all

the a_{i} above to equal zero) has no powers of x which appear with a nonzero coefficient; we leave

its degree undefined.

When the field F is the field of real or complex numbers , these definitions are
familiar, but

they work just as well over any field (e.g., Z/(p) for a prime p). Moreover, the
usual operations

of addition and multiplication for polynomials make sense in this general
context. For example,

let F = Z/(5), and de ne A,B ∈ F[x] by

A = 3x^{3} + x + 1, B = 4x + 2:

Then

A + B = 3x^{3} + 5x + 3 = 3x^{3} + 3

(recalling that 5 = 0 in Z/(5)) while

AB = 12x^{4} + 6x^{3} + 4x^{2} + 2x + 4x + 2

= 12x^{4} + 6x^{3} + 4x^{2} + 6x + 2

= 2x^{4} + x^{3} + 4x^{2} + x + 2:

With these definitions of +, . , the system F[x] becomes what is called a commutative ring:

• it is an abelian group under addition (with additive identity the polynomial 0),

• `. ' distributes over `+': for all A,B,C ∈ F[x], we have A(B + C) = AB + AC,

• there is a multiplicative identity (the constant polynomial 1),

•
multiplication is commutative (AB = BA for all A,B ∈ F[x]) and associative
(i.e.,

A(BC) = (AB)C for all A,B,C ∈ F[x]).

These properties look very close to the properties singled out in our definition
of a field. Nev-

ertheless, F[x] is not a field. In a field every nonzero element has an inverse, but
it turns out

that there are relatively few elements of F[x] which are invertible. We call
invertible elements

units.

Prev | Next |