1
00:00:12,770 --> 00:00:17,900
Good morning. My name is Ben Graham, and I lecture a second year course to our undergraduates on
2
00:00:17,900 --> 00:00:23,630
number three. Now, with the coronavirus crisis ongoing, we obviously can't give
3
00:00:23,630 --> 00:00:29,030
lectures in person in the usual way. And so what I've done this term for my lecture courses
4
00:00:29,030 --> 00:00:34,610
is to create so little podcasts of about 20, 30 minutes in length
5
00:00:34,610 --> 00:00:39,620
on the much the same topics that we would lecture. So I want to show you an example of that
6
00:00:39,620 --> 00:00:45,170
today. A podcast on the topic of primitive roots, which is a
7
00:00:45,170 --> 00:00:50,270
standard topic to cover in a first course in number theory. So you'll see that
8
00:00:50,270 --> 00:00:55,940
it consists of me talking over some slides, talking through the proofs and some of the concepts.
9
00:00:55,940 --> 00:01:01,100
And the students also have access to a full printed notes for the course, which give a few more details
10
00:01:01,100 --> 00:01:06,140
of some of the proofs, go over them carefully. So I hope you enjoy
11
00:01:06,140 --> 00:01:11,930
seeing how we're trying to deal with things in these very unusual times.
12
00:01:11,930 --> 00:01:17,040
Right. This is the second section in chapter three of the course. Chapter three of the course is
13
00:01:17,040 --> 00:01:22,190
about the multiplicative group Z, more cues that Star and this
14
00:01:22,190 --> 00:01:27,270
Section B is really going to be all about one theorem, which is the existence of
15
00:01:27,270 --> 00:01:32,280
primitive roots. That is to say, the fact that Z more piece, that
16
00:01:32,280 --> 00:01:37,590
star where Pierce subprime is a cyclic group will steitz everything Caerphilly later on.
17
00:01:37,590 --> 00:01:43,690
So this section is geared towards the proof of this, is there?
18
00:01:43,690 --> 00:01:48,860
So here is the statement. Let me be a prime. Then there is an element G.
19
00:01:48,860 --> 00:01:54,660
For some reason, these are always koochie in Z piece at Star with
20
00:01:54,660 --> 00:01:59,700
the order of G motion IP being P minus one. So that is to say the smallest
21
00:01:59,700 --> 00:02:04,770
positive integer n such that gta v and is covered to one modulate P is
22
00:02:04,770 --> 00:02:09,990
P minus one. And that's this. That's the largest that the order could possibly be.
23
00:02:09,990 --> 00:02:15,300
Because by firm as little theorem G to the P minus one is always
24
00:02:15,300 --> 00:02:22,490
one more P no matter what G is. So it's an element G with maximal order.
25
00:02:22,490 --> 00:02:27,860
Equivalently, this means that Z. more peace, that Starr is a cyclic group because that more peace and star
26
00:02:27,860 --> 00:02:33,110
is a group of size P minus one because five P, P minus one.
27
00:02:33,110 --> 00:02:39,260
And therefore, if there's an element of order P minus one, it must be a cyclic group of that size.
28
00:02:39,260 --> 00:02:44,260
So this is the main proposition that will be proving in this section.
29
00:02:44,260 --> 00:02:49,520
An element G with this property is called a primitive route mojado. And we use
30
00:02:49,520 --> 00:02:54,650
that word interchangeably for either an integer G whose
31
00:02:54,650 --> 00:03:03,520
reduction more P has this property or four elements of Z, more peace that start with this property.
32
00:03:03,520 --> 00:03:08,630
No. So if she is a primitive route, then a complete list of the elements of
33
00:03:08,630 --> 00:03:14,430
that more peace, that star is g.g squared
34
00:03:14,430 --> 00:03:19,530
up to cheat of the P minus two and one or more accurately, the co sets
35
00:03:19,530 --> 00:03:24,690
of peace and by those elements. So one plus peace and G plus peace and
36
00:03:24,690 --> 00:03:31,040
G squared plus peace. Add up to G to the P minus two plus peace at.
37
00:03:31,040 --> 00:03:36,170
Let's have a look at a little example. So when P is eleven, it said that the two is
38
00:03:36,170 --> 00:03:41,470
a primitive route. And that's because one, two, two square two cubed
39
00:03:41,470 --> 00:03:46,520
inside of the two to the nine turned out to be two distinct elements modulo eleven. And so that is
40
00:03:46,520 --> 00:03:51,650
a generator for Z model leavens that star, which is a slightly cyclic
41
00:03:51,650 --> 00:03:57,320
group of order. So those are the key statements about primitive roots.
42
00:03:57,320 --> 00:04:02,420
Now, before we get to the proof of the proposition itself, we need to take a detour into some
43
00:04:02,420 --> 00:04:07,460
results from ring theory about roots of polynomials. Some of them general and some of them
44
00:04:07,460 --> 00:04:12,750
more specific to the setting. So let's have a look at polynomial equations
45
00:04:12,750 --> 00:04:17,950
modulo prime. So I think, you know, the fact that quadratic equations
46
00:04:17,950 --> 00:04:22,960
over the reals have at most two routes, sometimes two, sometimes no. And over the
47
00:04:22,960 --> 00:04:28,110
complex, you see they have exactly two routes, it with multiplicity.
48
00:04:28,110 --> 00:04:33,880
But the analogue of this in that more cues add the rings, that more cues that can fail.
49
00:04:33,880 --> 00:04:40,150
So, for instance, if CU is age, equation X squared equals one
50
00:04:40,150 --> 00:04:45,310
has four solutions, modular eight, namely X equals one, three,
51
00:04:45,310 --> 00:04:51,430
five and seven. So for all of those Vardy's of X, X squared is Konger to one modulo eight.
52
00:04:51,430 --> 00:04:56,840
And so this fact that an equation of degree two has it most to reach is not a fact.
53
00:04:56,840 --> 00:05:01,890
In that more more it in general. But it is true when Q
54
00:05:01,890 --> 00:05:06,900
is a prime. So over Z, more PS and quadratic equations have
55
00:05:06,900 --> 00:05:12,130
at most two roots. And the key thing here is that Zebb more piece
56
00:05:12,130 --> 00:05:18,820
is actually an integral to Maine, so is to say it's a ring with no zero devices.
57
00:05:18,820 --> 00:05:24,220
In other words, if a B equals zero in that rings, if I B equals zero more P than either A
58
00:05:24,220 --> 00:05:29,650
zero or B zero. And actually, if you think about it, that is just a rephrasing
59
00:05:29,650 --> 00:05:34,740
of the property. Peeping prime therapy divides AP than either Pete,
60
00:05:34,740 --> 00:05:40,510
if I say or P divide P and as a matter of fact, Z more please. That is a field.
61
00:05:40,510 --> 00:05:45,580
It's more than an integral domain. It's a field since, as we've shown, all non-zero
62
00:05:45,580 --> 00:05:50,630
elements have investors. So we're working over a field, whereas Zemurray
63
00:05:50,630 --> 00:05:55,630
set is not an ethical domain. It does have some zera divisors. So for example, two times
64
00:05:55,630 --> 00:06:00,940
four is equal to zero. Moderate. So it's not identical to mine. Uncertainty
65
00:06:00,940 --> 00:06:06,690
is not a field. Let's state a general result
66
00:06:06,690 --> 00:06:11,810
about polynomial equations. So we're really interested in this result. Is that more
67
00:06:11,810 --> 00:06:17,670
piece, Ed, at the will states improve it in an arbitrary, integral domain?
68
00:06:17,670 --> 00:06:22,890
Because the proof is just the same. So let F of X be in the polynomial rate.
69
00:06:22,890 --> 00:06:27,960
Vigar of X of some integral domain are. And suppose that F is polynomial
70
00:06:27,960 --> 00:06:33,470
degree. De. Then the proposition is that F hasn't most deep roots
71
00:06:33,470 --> 00:06:39,250
in R. So here's the proof.
72
00:06:39,250 --> 00:06:44,300
So this is the most distinct route. I'm not talking about multiplicity here. So suppose
73
00:06:44,300 --> 00:06:49,520
that Alpha is a ruse. Suppose Alpha in big are satisfies, F of Alpha
74
00:06:49,520 --> 00:06:54,910
equals zero. Now by the division algorithm for polynomials,
75
00:06:54,910 --> 00:07:00,670
trying to write F as a multiple of X minus Alpha plus the remainder.
76
00:07:00,670 --> 00:07:05,760
You can do that with the remainder being a constant. So you can just do this by
77
00:07:05,760 --> 00:07:11,400
successively knocking at turns, starting from the largest degree term of F.
78
00:07:11,400 --> 00:07:16,530
Take the top coefficient of Q to be such that the top coefficient of
79
00:07:16,530 --> 00:07:21,720
X minus Alpha Times Q matches the top coefficient of that. And then keep working down
80
00:07:21,720 --> 00:07:27,660
through the degrees until you have a concept left at the end. So that's the division algorithm for polynomials,
81
00:07:27,660 --> 00:07:33,330
no matter what. Alpha is not using the fact that it's a root F of X is equal to X minus Alpha
82
00:07:33,330 --> 00:07:38,400
times cubed X plus a constant C for some polynomial Q
83
00:07:38,400 --> 00:07:43,660
and some constancy in this ethical domain. Are. Now, let's substitute
84
00:07:43,660 --> 00:07:48,700
Alpha into this expression on the left hand side. We get F of Alpha, which
85
00:07:48,700 --> 00:07:53,770
is zero by the assumption that Alpha is a root of that. And on the right hand side, we
86
00:07:53,770 --> 00:07:58,980
get alpha minus alpha times. Q Alpha, which is zero. Plus, see.
87
00:07:58,980 --> 00:08:03,980
And that must, of course, mean that C is zero. So we've shown the fact that they're the F
88
00:08:03,980 --> 00:08:10,010
of X is X minus Alpha times, Q of X for subcu.
89
00:08:10,010 --> 00:08:16,960
Now, let's take another route of this polynomial. So let's take another beta.
90
00:08:16,960 --> 00:08:22,540
And if I substitute that sense, what I now know, the F is zero
91
00:08:22,540 --> 00:08:27,810
and Alpha Beta is also beta minus alpha times cured beta.
92
00:08:27,810 --> 00:08:34,300
But if Peter really is another route to offer a better it's a strength, then alpha minus beta is not zero.
93
00:08:34,300 --> 00:08:39,490
And therefore, cure feature is here. And this is the point at which I've used the fact that Big R
94
00:08:39,490 --> 00:08:45,670
is an integral to make the product of two things which being equal to zero.
95
00:08:45,670 --> 00:08:52,190
And I'm forced to conclude that one of the two things is equal to zero. And it's definitely not alpha minus beta.
96
00:08:52,190 --> 00:08:57,340
So cute. PETA is Sarah. Now, if you proceed by induction on the degrees, Q
97
00:08:57,340 --> 00:09:03,710
is a polynomial degree T minus one. And so by induction has it most D minus one reads.
98
00:09:03,710 --> 00:09:09,750
And therefore, the reason F being the roots of Q together with Alpha,
99
00:09:09,750 --> 00:09:17,190
that has it most the distinct roots. So by adoption of the degree, I've proven the proposition.
100
00:09:17,190 --> 00:09:22,310
Hasn't missed one plus T minus one. With these roots. So that's polynomial
101
00:09:22,310 --> 00:09:28,310
equations modulate it over identical to mine. Now let's be a bit more specific
102
00:09:28,310 --> 00:09:33,650
to Z, more piece. So let's start another lemme loop another Lemmer about polynomial
103
00:09:33,650 --> 00:09:38,720
equations. So I suppose it pays a prime and suppose that deep divides
104
00:09:38,720 --> 00:09:43,870
people by this one. Then dilemma is that there are exactly these
105
00:09:43,870 --> 00:09:49,080
values of X and Z, more peace and such that X, the D Congress to one modulo
106
00:09:49,080 --> 00:09:54,200
P at most. Exactly. D. And
107
00:09:54,200 --> 00:09:59,440
here's the proof of that. Well, the key observation is that X to the D minus one
108
00:09:59,440 --> 00:10:04,630
is a factor of X to the P minus one, minus one. So this is a general property of polynomials.
109
00:10:04,630 --> 00:10:09,790
If A device B, X to A minus one, device X to the B on this one, and you can write
110
00:10:09,790 --> 00:10:14,830
down the factorisation explicitly in this case. So X to the P minus one,
111
00:10:14,830 --> 00:10:20,030
minus one is X to the D minus one times the polynomial G of X
112
00:10:20,030 --> 00:10:25,270
where G of X is just one plus of that, the sex of the two D plus up to X to be
113
00:10:25,270 --> 00:10:33,150
P minus one over T minus one times D. There's a very explicit factorisation.
114
00:10:33,150 --> 00:10:38,220
Now, here's the crucial observation, the polynomial on the left, X
115
00:10:38,220 --> 00:10:43,590
to the P minus one, minus one has a lot of roots by Furman's little theorem.
116
00:10:43,590 --> 00:10:48,750
In fact, everything in Z more piece, that star is the root of that polynomial. And that's P
117
00:10:48,750 --> 00:10:54,440
minus one. Different elements. So Excel P minus one. Minus one.
118
00:10:54,440 --> 00:10:59,670
Modular P. So in Z mouthpiece, it has P minus one distinct
119
00:10:59,670 --> 00:11:04,720
reads. And they must also, of course, be roots of the right hand
120
00:11:04,720 --> 00:11:11,030
side of the displayed equations. They've also got to be roots of activity minus one times G of X.
121
00:11:11,030 --> 00:11:16,280
But G is a polynomial degree. He minus one, minus three, and therefore
122
00:11:16,280 --> 00:11:21,500
by the results I showed on the last slide. It can't have more than T minus one Manistee
123
00:11:21,500 --> 00:11:26,510
roots. So if the P minus one root of the left hand side X
124
00:11:26,510 --> 00:11:32,260
minus one. Minus one. No more than P minus one. Manistee of them can be Rousso G.
125
00:11:32,260 --> 00:11:38,090
And that means that the other dy root got to be roots of X to the T minus one.
126
00:11:38,090 --> 00:11:43,340
So there are indeed at least three values of X, such that activity is connected
127
00:11:43,340 --> 00:11:48,470
to one moppy. And in fact, there are also at most the values of X with that property.
128
00:11:48,470 --> 00:11:53,720
Again, by the proposition on the last slide. So that concludes
129
00:11:53,720 --> 00:11:58,970
the proof of the love. And this was a little bit specific, what very specific to that Morillo piece that we really
130
00:11:58,970 --> 00:12:04,500
used Thurber's little theorem here.
131
00:12:04,500 --> 00:12:09,960
Now, then, we've assembled those ingredients of our polynomials. We'll turn to the actual proof
132
00:12:09,960 --> 00:12:15,050
of the existence of primitive roots. I we'll need another Lamma before we really get
133
00:12:15,050 --> 00:12:20,390
into the heart of it. So let people prime, let QB
134
00:12:20,390 --> 00:12:26,690
another prime. And suppose the key to the sea divides P minus one for something, which is C.
135
00:12:26,690 --> 00:12:31,760
And the conclusion is that there's an element A in the multiplicative group said more peace and
136
00:12:31,760 --> 00:12:39,580
star, whose order is exactly cuz of the policy.
137
00:12:39,580 --> 00:12:44,880
So let's have a look at the proof of that. By the lemma on the last slide,
138
00:12:44,880 --> 00:12:49,920
lemme three point four. They're a cue to the sea values of X that to satisfy X of the
139
00:12:49,920 --> 00:12:55,030
key to the sea is conquered to one modulo P. And we just need
140
00:12:55,030 --> 00:13:01,680
to show that they're not all elements of strictly smaller or order than cuz of the sea.
141
00:13:01,680 --> 00:13:06,840
So if I've got one of those X's and if it does not have all the keys of the C. Then
142
00:13:06,840 --> 00:13:12,530
we know by the basic properties of order that this order must divide to the.
143
00:13:12,530 --> 00:13:17,560
Because Q is a prime. If you've got something that divides cuz of the sea and is not
144
00:13:17,560 --> 00:13:22,810
key to the sea, then it must divide cuz of the sea minus one. Said X
145
00:13:22,810 --> 00:13:27,960
is an element. Satisfy X are the key to the C is Congress to one more
146
00:13:27,960 --> 00:13:33,170
P, but which does not have order cuz of the C than
147
00:13:33,170 --> 00:13:38,230
its order must divide. Cuz of the C minus one. And therefore that element X satisfies the
148
00:13:38,230 --> 00:13:44,590
polynomial equation. X to the Q to the C minus one is Congress to one p.
149
00:13:44,590 --> 00:13:51,580
But that polynomial equation has at most, in fact, exactly of the C minus one roots.
150
00:13:51,580 --> 00:13:56,600
So the number of elements that have that property as it is, keeps it the seamless one. And
151
00:13:56,600 --> 00:14:01,760
what this means is that of the cues of the sea elements of X satisfying X of the cue to the sea being
152
00:14:01,760 --> 00:14:07,730
conquered to one P only, Q to the C minus one of them, which is a strictly smaller number.
153
00:14:07,730 --> 00:14:12,800
Do not have order cues of the C. So, in fact, there are key to the C
154
00:14:12,800 --> 00:14:17,810
minus cuz of the C minus one, which is a positive number elements X, whose
155
00:14:17,810 --> 00:14:25,980
order is exactly key to the C and not least the proof of the number.
156
00:14:25,980 --> 00:14:31,150
So let's continue with the proof of the existence of primitive roots. And here's just a restatement to remind you
157
00:14:31,150 --> 00:14:36,160
of what we're trying to prove. So this is Proposition three point two. The statement is that there's an element
158
00:14:36,160 --> 00:14:41,320
G in Z, my piece that star pairs of pride, whose order is exactly
159
00:14:41,320 --> 00:14:46,570
P minus one. And we're just going to combine a whole load of results
160
00:14:46,570 --> 00:14:52,460
that we've already proven. So we'll factor P minus one.
161
00:14:52,460 --> 00:14:57,500
Let's factor it into products of distinct from powers. So it's key. Wanted to
162
00:14:57,500 --> 00:15:03,410
see one. Time's up. Acute case of the S.K. where the KEYT are distinct primes.
163
00:15:03,410 --> 00:15:08,550
By the Lemmer on the last slide, there are elements
164
00:15:08,550 --> 00:15:13,610
in that piece that star with the order of a more P being QIC,
165
00:15:13,610 --> 00:15:18,620
the CIA. So if any prime power, there's an element in several peace and star with that
166
00:15:18,620 --> 00:15:23,890
order. That's what we showed. Take
167
00:15:23,890 --> 00:15:29,890
a to be the product of those elements a one times up to AK. Then the final Lemmer
168
00:15:29,890 --> 00:15:35,050
proven in Section three A was this one. Number three. Point three.
169
00:15:35,050 --> 00:15:40,180
It states that if I've got two elements, a one and a two of orders, this led one
170
00:15:40,180 --> 00:15:45,190
a little and too much like you. And if those orders are co prime, then there is
171
00:15:45,190 --> 00:15:50,230
an element specifically the product I want time say, to whose order is the products of the little
172
00:15:50,230 --> 00:15:55,620
Ani's? And if I apply this Lemmer here with
173
00:15:55,620 --> 00:16:00,780
the products of all of the eyes. So if I apply the label repeatedly, what I get is that the
174
00:16:00,780 --> 00:16:05,850
order of A will be the product. If the orders of the eyes. So the
175
00:16:05,850 --> 00:16:11,130
order of a A being a one time that the ACA is the product
176
00:16:11,130 --> 00:16:16,260
of the orders of the eyes. That is to say, the products of the KEYT to the sea ice,
177
00:16:16,260 --> 00:16:21,540
which by design is exactly P minus one. So I have exhibited an element,
178
00:16:21,540 --> 00:16:26,640
A whose order is P minus one. That is to say a primitive route
179
00:16:26,640 --> 00:16:32,160
or a generator for Satmar peace and star as a cyclic group, not conclusive
180
00:16:32,160 --> 00:16:37,170
the proof of the existence of primitive roots, which was the main business of this section.
181
00:16:37,170 --> 00:16:42,190
And that tells us what the structure of that piece, that star is as a group. It's a
182
00:16:42,190 --> 00:16:47,310
cyclic group of water. It's one. Now, it's often useful to know. You may find yourself wanting
183
00:16:47,310 --> 00:16:53,250
to know what is the structure of Z cues that star for an arbitrary queue.
184
00:16:53,250 --> 00:16:58,440
This is something that's not an examinable topic, but you'll find fairly full set of notes
185
00:16:58,440 --> 00:17:03,480
on it in the printed notes for the course. I'm not going to go over all of the proofs now, but
186
00:17:03,480 --> 00:17:08,610
let me just tell you what the crucial statements are. So this is about the structure of Z, not cues at Star,
187
00:17:08,610 --> 00:17:13,870
where Q is not A prime. Well, the first thing to observe is that to understand the structure
188
00:17:13,870 --> 00:17:19,540
of that group, it suffices to understand what happens in the case when Q is a prime power.
189
00:17:19,540 --> 00:17:24,970
Because if I factor Q as a product of prime powers in Z cuz ed star factors
190
00:17:24,970 --> 00:17:30,310
as the product is isomorphic to the product of the Z, P
191
00:17:30,310 --> 00:17:35,810
to the R eyes at stars, if P to the RIAA, those price power factors.
192
00:17:35,810 --> 00:17:40,820
And this follows from the multiplicative Chinese. So it suffices to understand the
193
00:17:40,820 --> 00:17:46,060
prime part Kate. Now, here's one key result about that. It turns
194
00:17:46,060 --> 00:17:51,310
out that actually primitive roots exist, mosiello, odd prime. So this is a therapy
195
00:17:51,310 --> 00:17:56,390
that is an elaboration of the existence of primitive roots modulo P. The full
196
00:17:56,390 --> 00:18:01,590
proof you'll find in the notes appears in our prime. And if all is an exponent tracing,
197
00:18:01,590 --> 00:18:07,810
they're equal to one, then Z. More piece of the offset star is a cyclic group.
198
00:18:07,810 --> 00:18:12,910
And then there's a little wrinkle, which is that when P is not an our prime. In other words, when P
199
00:18:12,910 --> 00:18:17,920
is two, that's no longer the case. So Z, more to to the
200
00:18:17,920 --> 00:18:23,090
case at Star. Is not quite sight like it's isomorphic to the products of Acyclic Group
201
00:18:23,090 --> 00:18:28,400
of Order two and acyclic group of order two to the K minus to.
202
00:18:28,400 --> 00:18:33,740
And again, you'll find proof of this fact in the printed notes.
203
00:18:33,740 --> 00:18:38,840
That cycling group devoted to to the came on, too. As it turns out, it's generated by five.
204
00:18:38,840 --> 00:18:47,510
So five was it's not quite a primitive route modulo two to the K is as close as you're going to get.
205
00:18:47,510 --> 00:18:52,520
If you put those two lives together and do a little bit of elementary group theory, you come
206
00:18:52,520 --> 00:18:57,790
out with the following proposition, which is the only values of Q four, which is add more cues,
207
00:18:57,790 --> 00:19:02,800
that star is a slightly crude. Are tuned for. The
208
00:19:02,800 --> 00:19:08,200
odd prime powers or twice the prime powers. So a primitive
209
00:19:08,200 --> 00:19:13,230
route exists only for those bodies of cute. So that's a very brief,
210
00:19:13,230 --> 00:19:18,360
whirlwind tour of the properties, of the structure of that molecule, that star. When
211
00:19:18,360 --> 00:19:23,380
Hugh is more general than just the prime.
212
00:19:23,380 --> 00:19:29,350
Well, that's the end of Chapter three in Chapter four, tell you something quite different. We'll talk about
213
00:19:29,350 --> 00:19:54,960
quadratic residues and in particular, proof the famous law of quadratic reciprocity.