Good morning. My name is Ben Graham, and I lecture a second year course to our undergraduates on
number three. Now, with the coronavirus crisis ongoing, we obviously can't give
lectures in person in the usual way. And so what I've done this term for my lecture courses
is to create so little podcasts of about 20, 30 minutes in length
on the much the same topics that we would lecture. So I want to show you an example of that
today. A podcast on the topic of primitive roots, which is a
standard topic to cover in a first course in number theory. So you'll see that
it consists of me talking over some slides, talking through the proofs and some of the concepts.
And the students also have access to a full printed notes for the course, which give a few more details
of some of the proofs, go over them carefully. So I hope you enjoy
seeing how we're trying to deal with things in these very unusual times.
Right. This is the second section in chapter three of the course. Chapter three of the course is
about the multiplicative group Z, more cues that Star and this
Section B is really going to be all about one theorem, which is the existence of
primitive roots. That is to say, the fact that Z more piece, that
star where Pierce subprime is a cyclic group will steitz everything Caerphilly later on.
So this section is geared towards the proof of this, is there?
So here is the statement. Let me be a prime. Then there is an element G.
For some reason, these are always koochie in Z piece at Star with
the order of G motion IP being P minus one. So that is to say the smallest
positive integer n such that gta v and is covered to one modulate P is
P minus one. And that's this. That's the largest that the order could possibly be.
Because by firm as little theorem G to the P minus one is always
one more P no matter what G is. So it's an element G with maximal order.
Equivalently, this means that Z. more peace, that Starr is a cyclic group because that more peace and star
is a group of size P minus one because five P, P minus one.
And therefore, if there's an element of order P minus one, it must be a cyclic group of that size.
So this is the main proposition that will be proving in this section.
An element G with this property is called a primitive route mojado. And we use
that word interchangeably for either an integer G whose
reduction more P has this property or four elements of Z, more peace that start with this property.
No. So if she is a primitive route, then a complete list of the elements of
that more peace, that star is g.g squared
up to cheat of the P minus two and one or more accurately, the co sets
of peace and by those elements. So one plus peace and G plus peace and
G squared plus peace. Add up to G to the P minus two plus peace at.
Let's have a look at a little example. So when P is eleven, it said that the two is
a primitive route. And that's because one, two, two square two cubed
inside of the two to the nine turned out to be two distinct elements modulo eleven. And so that is
a generator for Z model leavens that star, which is a slightly cyclic
group of order. So those are the key statements about primitive roots.
Now, before we get to the proof of the proposition itself, we need to take a detour into some
results from ring theory about roots of polynomials. Some of them general and some of them
more specific to the setting. So let's have a look at polynomial equations
modulo prime. So I think, you know, the fact that quadratic equations
over the reals have at most two routes, sometimes two, sometimes no. And over the
complex, you see they have exactly two routes, it with multiplicity.
But the analogue of this in that more cues add the rings, that more cues that can fail.
So, for instance, if CU is age, equation X squared equals one
has four solutions, modular eight, namely X equals one, three,
five and seven. So for all of those Vardy's of X, X squared is Konger to one modulo eight.
And so this fact that an equation of degree two has it most to reach is not a fact.
In that more more it in general. But it is true when Q
is a prime. So over Z, more PS and quadratic equations have
at most two roots. And the key thing here is that Zebb more piece
is actually an integral to Maine, so is to say it's a ring with no zero devices.
In other words, if a B equals zero in that rings, if I B equals zero more P than either A
zero or B zero. And actually, if you think about it, that is just a rephrasing
of the property. Peeping prime therapy divides AP than either Pete,
if I say or P divide P and as a matter of fact, Z more please. That is a field.
It's more than an integral domain. It's a field since, as we've shown, all non-zero
elements have investors. So we're working over a field, whereas Zemurray
set is not an ethical domain. It does have some zera divisors. So for example, two times
four is equal to zero. Moderate. So it's not identical to mine. Uncertainty
is not a field. Let's state a general result
about polynomial equations. So we're really interested in this result. Is that more
piece, Ed, at the will states improve it in an arbitrary, integral domain?
Because the proof is just the same. So let F of X be in the polynomial rate.
Vigar of X of some integral domain are. And suppose that F is polynomial
degree. De. Then the proposition is that F hasn't most deep roots
in R. So here's the proof.
So this is the most distinct route. I'm not talking about multiplicity here. So suppose
that Alpha is a ruse. Suppose Alpha in big are satisfies, F of Alpha
equals zero. Now by the division algorithm for polynomials,
trying to write F as a multiple of X minus Alpha plus the remainder.
You can do that with the remainder being a constant. So you can just do this by
successively knocking at turns, starting from the largest degree term of F.
Take the top coefficient of Q to be such that the top coefficient of
X minus Alpha Times Q matches the top coefficient of that. And then keep working down
through the degrees until you have a concept left at the end. So that's the division algorithm for polynomials,
no matter what. Alpha is not using the fact that it's a root F of X is equal to X minus Alpha
times cubed X plus a constant C for some polynomial Q
and some constancy in this ethical domain. Are. Now, let's substitute
Alpha into this expression on the left hand side. We get F of Alpha, which
is zero by the assumption that Alpha is a root of that. And on the right hand side, we
get alpha minus alpha times. Q Alpha, which is zero. Plus, see.
And that must, of course, mean that C is zero. So we've shown the fact that they're the F
of X is X minus Alpha times, Q of X for subcu.
Now, let's take another route of this polynomial. So let's take another beta.
And if I substitute that sense, what I now know, the F is zero
and Alpha Beta is also beta minus alpha times cured beta.
But if Peter really is another route to offer a better it's a strength, then alpha minus beta is not zero.
And therefore, cure feature is here. And this is the point at which I've used the fact that Big R
is an integral to make the product of two things which being equal to zero.
And I'm forced to conclude that one of the two things is equal to zero. And it's definitely not alpha minus beta.
So cute. PETA is Sarah. Now, if you proceed by induction on the degrees, Q
is a polynomial degree T minus one. And so by induction has it most D minus one reads.
And therefore, the reason F being the roots of Q together with Alpha,
that has it most the distinct roots. So by adoption of the degree, I've proven the proposition.
Hasn't missed one plus T minus one. With these roots. So that's polynomial
equations modulate it over identical to mine. Now let's be a bit more specific
to Z, more piece. So let's start another lemme loop another Lemmer about polynomial
equations. So I suppose it pays a prime and suppose that deep divides
people by this one. Then dilemma is that there are exactly these
values of X and Z, more peace and such that X, the D Congress to one modulo
P at most. Exactly. D. And
here's the proof of that. Well, the key observation is that X to the D minus one
is a factor of X to the P minus one, minus one. So this is a general property of polynomials.
If A device B, X to A minus one, device X to the B on this one, and you can write
down the factorisation explicitly in this case. So X to the P minus one,
minus one is X to the D minus one times the polynomial G of X
where G of X is just one plus of that, the sex of the two D plus up to X to be
P minus one over T minus one times D. There's a very explicit factorisation.
Now, here's the crucial observation, the polynomial on the left, X
to the P minus one, minus one has a lot of roots by Furman's little theorem.
In fact, everything in Z more piece, that star is the root of that polynomial. And that's P
minus one. Different elements. So Excel P minus one. Minus one.
Modular P. So in Z mouthpiece, it has P minus one distinct
reads. And they must also, of course, be roots of the right hand
side of the displayed equations. They've also got to be roots of activity minus one times G of X.
But G is a polynomial degree. He minus one, minus three, and therefore
by the results I showed on the last slide. It can't have more than T minus one Manistee
roots. So if the P minus one root of the left hand side X
minus one. Minus one. No more than P minus one. Manistee of them can be Rousso G.
And that means that the other dy root got to be roots of X to the T minus one.
So there are indeed at least three values of X, such that activity is connected
to one moppy. And in fact, there are also at most the values of X with that property.
Again, by the proposition on the last slide. So that concludes
the proof of the love. And this was a little bit specific, what very specific to that Morillo piece that we really
used Thurber's little theorem here.
Now, then, we've assembled those ingredients of our polynomials. We'll turn to the actual proof
of the existence of primitive roots. I we'll need another Lamma before we really get
into the heart of it. So let people prime, let QB
another prime. And suppose the key to the sea divides P minus one for something, which is C.
And the conclusion is that there's an element A in the multiplicative group said more peace and
star, whose order is exactly cuz of the policy.
So let's have a look at the proof of that. By the lemma on the last slide,
lemme three point four. They're a cue to the sea values of X that to satisfy X of the
key to the sea is conquered to one modulo P. And we just need
to show that they're not all elements of strictly smaller or order than cuz of the sea.
So if I've got one of those X's and if it does not have all the keys of the C. Then
we know by the basic properties of order that this order must divide to the.
Because Q is a prime. If you've got something that divides cuz of the sea and is not
key to the sea, then it must divide cuz of the sea minus one. Said X
is an element. Satisfy X are the key to the C is Congress to one more
P, but which does not have order cuz of the C than
its order must divide. Cuz of the C minus one. And therefore that element X satisfies the
polynomial equation. X to the Q to the C minus one is Congress to one p.
But that polynomial equation has at most, in fact, exactly of the C minus one roots.
So the number of elements that have that property as it is, keeps it the seamless one. And
what this means is that of the cues of the sea elements of X satisfying X of the cue to the sea being
conquered to one P only, Q to the C minus one of them, which is a strictly smaller number.
Do not have order cues of the C. So, in fact, there are key to the C
minus cuz of the C minus one, which is a positive number elements X, whose
order is exactly key to the C and not least the proof of the number.
So let's continue with the proof of the existence of primitive roots. And here's just a restatement to remind you
of what we're trying to prove. So this is Proposition three point two. The statement is that there's an element
G in Z, my piece that star pairs of pride, whose order is exactly
P minus one. And we're just going to combine a whole load of results
that we've already proven. So we'll factor P minus one.
Let's factor it into products of distinct from powers. So it's key. Wanted to
see one. Time's up. Acute case of the S.K. where the KEYT are distinct primes.
By the Lemmer on the last slide, there are elements
in that piece that star with the order of a more P being QIC,
the CIA. So if any prime power, there's an element in several peace and star with that
order. That's what we showed. Take
a to be the product of those elements a one times up to AK. Then the final Lemmer
proven in Section three A was this one. Number three. Point three.
It states that if I've got two elements, a one and a two of orders, this led one
a little and too much like you. And if those orders are co prime, then there is
an element specifically the product I want time say, to whose order is the products of the little
Ani's? And if I apply this Lemmer here with
the products of all of the eyes. So if I apply the label repeatedly, what I get is that the
order of A will be the product. If the orders of the eyes. So the
order of a A being a one time that the ACA is the product
of the orders of the eyes. That is to say, the products of the KEYT to the sea ice,
which by design is exactly P minus one. So I have exhibited an element,
A whose order is P minus one. That is to say a primitive route
or a generator for Satmar peace and star as a cyclic group, not conclusive
the proof of the existence of primitive roots, which was the main business of this section.
And that tells us what the structure of that piece, that star is as a group. It's a
cyclic group of water. It's one. Now, it's often useful to know. You may find yourself wanting
to know what is the structure of Z cues that star for an arbitrary queue.
This is something that's not an examinable topic, but you'll find fairly full set of notes
on it in the printed notes for the course. I'm not going to go over all of the proofs now, but
let me just tell you what the crucial statements are. So this is about the structure of Z, not cues at Star,
where Q is not A prime. Well, the first thing to observe is that to understand the structure
of that group, it suffices to understand what happens in the case when Q is a prime power.
Because if I factor Q as a product of prime powers in Z cuz ed star factors
as the product is isomorphic to the product of the Z, P
to the R eyes at stars, if P to the RIAA, those price power factors.
And this follows from the multiplicative Chinese. So it suffices to understand the
prime part Kate. Now, here's one key result about that. It turns
out that actually primitive roots exist, mosiello, odd prime. So this is a therapy
that is an elaboration of the existence of primitive roots modulo P. The full
proof you'll find in the notes appears in our prime. And if all is an exponent tracing,
they're equal to one, then Z. More piece of the offset star is a cyclic group.
And then there's a little wrinkle, which is that when P is not an our prime. In other words, when P
is two, that's no longer the case. So Z, more to to the
case at Star. Is not quite sight like it's isomorphic to the products of Acyclic Group
of Order two and acyclic group of order two to the K minus to.
And again, you'll find proof of this fact in the printed notes.
That cycling group devoted to to the came on, too. As it turns out, it's generated by five.
So five was it's not quite a primitive route modulo two to the K is as close as you're going to get.
If you put those two lives together and do a little bit of elementary group theory, you come
out with the following proposition, which is the only values of Q four, which is add more cues,
that star is a slightly crude. Are tuned for. The
odd prime powers or twice the prime powers. So a primitive
route exists only for those bodies of cute. So that's a very brief,
whirlwind tour of the properties, of the structure of that molecule, that star. When
Hugh is more general than just the prime.
Well, that's the end of Chapter three in Chapter four, tell you something quite different. We'll talk about
quadratic residues and in particular, proof the famous law of quadratic reciprocity.