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.