1 00:00:00,000 --> 00:00:04,566 The last thing I want to talk about this week 
is the Fundamental Theorem of Arithmetic. 2 00:00:04,566 --> 00:00:06,600 So I always joke with 
students and I say 3 00:00:06,600 --> 00:00:11,233 you know, “If something is called the Fundamental Theorem of something, 4 00:00:11,233 --> 00:00:12,933 you know insert 
subject name here, 5 00:00:12,933 --> 00:00:16,000 you should probably know it. You should 
probably know it inside out, you should 6 00:00:16,000 --> 00:00:18,700 know it frontwards, 
backwards, 7 00:00:18,700 --> 00:00:21,600 in different languages, you should 
just know the theorem, okay?” 8 00:00:21,600 --> 00:00:24,000 It's probably important. 9 00:00:24,000 --> 00:00:25,800 10 00:00:25,800 --> 00:00:28,933 So what do we need to do this? So we want to 
prove the Fundamental Theorem of Arithmetic, 11 00:00:28,933 --> 00:00:31,400 which we'll get to in the next 
slide, but before we do that 12 00:00:31,400 --> 00:00:33,900 we’re going to need a couple 
of tools that we don't have yet, 13 00:00:33,900 --> 00:00:36,000 so we're going to assume 
these for granted and 14 00:00:36,000 --> 00:00:39,666 in the following week, we'll talk 
about the proofs of these things. 15 00:00:39,666 --> 00:00:41,400 So the first thing is called - 16 00:00:41,400 --> 00:00:43,866 the first thing that we’ll need is Euclid's Lemma, 17 00:00:43,866 --> 00:00:46,833 and in our notes we call 
it Primes and Divisibility, 18 00:00:46,833 --> 00:00:49,733 for now. I'm hoping just to get 
this changed to Euclid's Lemma. 19 00:00:49,733 --> 00:00:52,000 This is the name of 
the theorem in general, 20 00:00:52,000 --> 00:00:56,400 but in this course we've called it Primes and 
Divisibility and we use the acronym, PAD. 21 00:00:56,400 --> 00:00:59,133 So let a and b be integers and let p be a prime number. 22 00:00:59,133 --> 00:01:02,000 If p divides a product, 
then p must divide 23 00:01:02,000 --> 00:01:04,000 one of the two 
terms in the product. 24 00:01:04,000 --> 00:01:05,733 25 00:01:05,733 --> 00:01:07,966 This seems really 
obvious. If like 26 00:01:07,966 --> 00:01:10,900 7 divides, you know, 14 times 20, 27 00:01:10,900 --> 00:01:13,433 then 7 must divide 14 
or 7 must divide 20. 28 00:01:13,433 --> 00:01:16,000 It feels really obvious, 
but it's actually not 29 00:01:16,000 --> 00:01:18,000 completely 
trivial to prove. 30 00:01:18,000 --> 00:01:21,033 There's actually a little bit of thought that has to go into this proof. 31 00:01:21,033 --> 00:01:22,700 32 00:01:22,700 --> 00:01:24,066 But we'll see 
that next week. 33 00:01:24,066 --> 00:01:26,166 This actually will follow 
quite nicely from our work 34 00:01:26,166 --> 00:01:28,266 with greatest common divisor, 
which is where we're going. 35 00:01:28,266 --> 00:01:31,333 Our goal is to prove this 
basically next week. 36 00:01:31,333 --> 00:01:33,666 And a corollary from this, 
and this is actually in the 37 00:01:33,666 --> 00:01:36,000 January 2016 term 
we actually will get 38 00:01:36,000 --> 00:01:38,866 you to prove this; this Generalized Euclid’s Lemma, 39 00:01:38,866 --> 00:01:40,800 so if I have 40 00:01:40,800 --> 00:01:43,566 a bunch of integers, so a1, 
a2, all the way up to a n 41 00:01:43,566 --> 00:01:45,000 and some prime 
number p, 42 00:01:45,000 --> 00:01:47,366 then if p divides the 
product of these numbers, 43 00:01:47,366 --> 00:01:49,666 then p must divide 
one of the terms 44 00:01:49,666 --> 00:01:52,233 for some i 
between 1 and n. 45 00:01:52,233 --> 00:01:53,066 46 00:01:53,066 --> 00:01:56,000 It could divide more than one term, 
but it must divide at least one. 47 00:01:56,000 --> 00:01:57,800 48 00:01:57,800 --> 00:02:00,933 It turns out this Generalized Euclid’s 
Lemma is really what we're going to need. 49 00:02:00,933 --> 00:02:04,000 This follows quite nicely from Euclid's 
Lemma and I won't say anything more 50 00:02:04,000 --> 00:02:05,833 other than this 
because you'll have to - 51 00:02:05,833 --> 00:02:08,000 well because at least in one class we’ll prove it, 52 00:02:08,000 --> 00:02:09,433 but... 53 00:02:09,433 --> 00:02:10,700 that's it. 54 00:02:10,700 --> 00:02:13,166 So let's go through these. 
So with these tools, 55 00:02:13,166 --> 00:02:16,266 again, so the Generalized Euclid’s 
Lemma just keep in your mind, 56 00:02:16,266 --> 00:02:20,600 if a prime divides a product, then it must divide one of the things in the product. 57 00:02:20,600 --> 00:02:22,300 That's all it says. 58 00:02:22,300 --> 00:02:25,066 So if p divides… so 59 00:02:25,066 --> 00:02:28,900 p is let's say 3 and it 
divides 4 times 9, times 16, 60 00:02:28,900 --> 00:02:31,866 then 3 must divide 
one of 4, 9, or, 16. 61 00:02:31,866 --> 00:02:35,833 Possibly more than one. In the 
case of 2, 2 divides 4 and 16. 62 00:02:35,833 --> 00:02:38,600 But it must divide 
at least one. 63 00:02:38,600 --> 00:02:40,300 64 00:02:40,300 --> 00:02:42,466 Fundamental Theorem 
of Arithmetic, what is it? 65 00:02:42,466 --> 00:02:43,233 66 00:02:43,233 --> 00:02:44,433 Here it is. 67 00:02:44,433 --> 00:02:47,300 Sometimes it's called Unique Factorization Theorem. 68 00:02:47,300 --> 00:02:49,433 So that's why we use 
the abbreviation UFT. 69 00:02:49,433 --> 00:02:51,633 We’ll see that FTA 
will be reserved 70 00:02:51,633 --> 00:02:54,366 for another fundamental 
theorem later in the course. 71 00:02:54,366 --> 00:02:55,700 72 00:02:55,700 --> 00:02:58,966 So what does UFT say? What does the 
Fundamental Theorem of Arithmetic say? 73 00:02:58,966 --> 00:03:00,933 Every… bad 
pluralization here… 74 00:03:00,933 --> 00:03:04,266 every integer n greater than 
1, can be factored uniquely 75 00:03:04,266 --> 00:03:07,566 into a product of primes, so product of prime numbers. 76 00:03:07,566 --> 00:03:09,133 77 00:03:09,133 --> 00:03:12,000 Every number can be 
factored into primes. 78 00:03:12,000 --> 00:03:13,800 79 00:03:13,800 --> 00:03:16,566 And I say uniquely here, I 
actually don't mean uniquely. 80 00:03:16,566 --> 00:03:19,133 I mean uniquely up to 
reordering of the primes. 81 00:03:19,133 --> 00:03:21,633 So I should be a little bit 
careful here, I'll update that 82 00:03:21,633 --> 00:03:24,000 83 00:03:24,000 --> 00:03:25,200 in the PDF. 84 00:03:25,200 --> 00:03:28,533 So every integer - and I'll fix the 
typo - every integer n greater than 1 85 00:03:28,533 --> 00:03:32,233 can be factored uniquely into 
a product of prime numbers 86 00:03:32,233 --> 00:03:34,000 up to reordering 
of the primes. 87 00:03:34,000 --> 00:03:36,000 So for example, if I 
have the number 6, 88 00:03:36,000 --> 00:03:39,533 right, I can write that as 2 times 
3, or I can write that as 3 times 2. 89 00:03:39,533 --> 00:03:41,400 Those really aren't different. I mean 90 00:03:41,400 --> 00:03:44,166 those should be the same thing, 
you shouldn't count that twice. 91 00:03:44,166 --> 00:03:46,066 So up to that 
reordering, 92 00:03:46,066 --> 00:03:49,600 6 can be uniquely factored as 2 
times 3. The prime numbers 2 and 3. 93 00:03:49,600 --> 00:03:52,000 94 00:03:52,000 --> 00:03:54,233 By convention - so 
something else to mention - 95 00:03:54,233 --> 00:03:57,166 by convention, primes are just said 
to be a single element product. 96 00:03:57,166 --> 00:03:59,066 This is really just a technicality. 97 00:03:59,066 --> 00:04:04,000 You could include every integer n greater than 
1 is either prime, or can be factored uniquely 98 00:04:04,000 --> 00:04:06,966 into a product of primes up 
to reordering, that's fine too. 99 00:04:06,966 --> 00:04:10,333 This is just usually the way it's stated, 
so I'm going to leave it as so. 100 00:04:10,333 --> 00:04:12,633 101 00:04:12,633 --> 00:04:14,500 Okay. 102 00:04:14,500 --> 00:04:18,233 So again, what's the idea behind 
this? So if you factor a number… 103 00:04:18,233 --> 00:04:21,166 so I always use this analogy, 
if you factor a number in 104 00:04:21,166 --> 00:04:24,200 Canada, and your buddy in 
Australia factors a number, 105 00:04:24,200 --> 00:04:26,866 you should have them put the 
same factorization into primes, 106 00:04:26,866 --> 00:04:28,433 up to reordering 
of the primes. 107 00:04:28,433 --> 00:04:29,566 108 00:04:29,566 --> 00:04:31,633 Let's see the proof. 109 00:04:31,633 --> 00:04:33,200 So existence. 110 00:04:33,200 --> 00:04:34,500 111 00:04:34,500 --> 00:04:37,066 Before I go through this proof, 112 00:04:37,066 --> 00:04:41,600 existence: you can prove this by the Well 
Ordering Principle or by Mathematical Induction. 113 00:04:41,600 --> 00:04:44,000 If you've seen one way in class, I suggest you should pause the video 114 00:04:44,000 --> 00:04:46,333 and try using the other 
principle. Challenge yourself, 115 00:04:46,333 --> 00:04:48,000 see if you can actually do this. 116 00:04:48,000 --> 00:04:51,500 But for now, let's just talk about 
the proof existence and uniqueness. 117 00:04:51,500 --> 00:04:53,733 So assume towards a 
contradiction that not all numbers 118 00:04:53,733 --> 00:04:56,500 can be factored into 
a product of primes. 119 00:04:56,500 --> 00:04:59,666 So there's going to be some 
number, some numbers, 120 00:04:59,666 --> 00:05:02,033 that cannot be factored 
into a product of primes. 121 00:05:02,033 --> 00:05:05,066 So the set of all numbers that can't be 
factored into primes is non empty. 122 00:05:05,066 --> 00:05:07,366 Well because it's non empty, well 
by the Well Ordering Principle, 123 00:05:07,366 --> 00:05:09,266 there must be a 
smallest such number. 124 00:05:09,266 --> 00:05:11,333 I'm going to call 
that number n. 125 00:05:11,333 --> 00:05:13,000 126 00:05:13,000 --> 00:05:15,633 Then either n is prime, and 
that's a contradiction, right? 127 00:05:15,633 --> 00:05:19,200 Again, we said 
primes are just 128 00:05:19,200 --> 00:05:24,000 single element prime 
factorizations, that's fine. 129 00:05:24,000 --> 00:05:25,866 Well what's the alternative? 
Or n is composite, 130 00:05:25,866 --> 00:05:28,000 and we're going to write n 
is equal to a times b, 131 00:05:28,000 --> 00:05:30,633 where both a and b are 
strictly between 1 and n. 132 00:05:30,633 --> 00:05:31,833 133 00:05:31,833 --> 00:05:34,233 So what does that mean? 
Well by the minimality of n, 134 00:05:34,233 --> 00:05:36,533 both of a and 
b must be able 135 00:05:36,533 --> 00:05:38,266 to be factored as product of primes. 136 00:05:38,266 --> 00:05:40,000 They're less than 
n, bigger than 1, 137 00:05:40,000 --> 00:05:43,566 so they satisfy that the statement, 
or the hypothesis of the 138 00:05:43,566 --> 00:05:44,800 Fundamental Theorem of Arithmetic. 139 00:05:44,800 --> 00:05:47,566 So I must be able to factor 
them into a product of primes. 140 00:05:47,566 --> 00:05:49,066 141 00:05:49,066 --> 00:05:51,466 So if I can factor a and b as a 
product of primes, then n, which is 142 00:05:51,466 --> 00:05:53,733 the product of a and 
b, must also be 143 00:05:53,733 --> 00:05:56,366 able to be factored into 
a product of primes. 144 00:05:56,366 --> 00:05:59,400 But that doesn't make sense because 
we said that n couldn't be factored 145 00:05:59,400 --> 00:06:01,500 into a product of primes, 
and that's a contradiction. 146 00:06:01,500 --> 00:06:02,733 147 00:06:02,733 --> 00:06:05,966 So hence, every number can be factored 
into a product of prime numbers. 148 00:06:05,966 --> 00:06:06,966 149 00:06:06,966 --> 00:06:08,266 So that's part one. 150 00:06:08,266 --> 00:06:11,000 I mentioned nothing about 
the uniqueness here though. 151 00:06:11,000 --> 00:06:13,066 So how do we deal 
with uniqueness? 152 00:06:13,066 --> 00:06:15,333 And that can be 
done as follows. 153 00:06:15,333 --> 00:06:16,900 154 00:06:16,900 --> 00:06:20,000 So here I'm going to do an 
informal proof of uniqueness. 155 00:06:20,000 --> 00:06:22,500 In class I decided to 
do a formal proof 156 00:06:22,500 --> 00:06:23,333 157 00:06:23,333 --> 00:06:26,800 and after some pondering I thought,
"Well maybe I should do the informal proof 158 00:06:26,800 --> 00:06:30,266 in class now. Maybe save the formal proof for later." 159 00:06:30,266 --> 00:06:32,733 That being said, let's take a 
look at an informal proof 160 00:06:32,733 --> 00:06:35,466 of how this works. I feel like 
you're going to get an idea of how 161 00:06:35,466 --> 00:06:39,300 the uniqueness part of the Fundamental Theorem of Arithmetic really works. 162 00:06:39,300 --> 00:06:41,900 So we're going to suppose 
that n can be factored in 163 00:06:41,900 --> 00:06:44,166 two distinct 
ways. So it, 164 00:06:44,166 --> 00:06:45,933 you know, it could 
have been… 165 00:06:45,933 --> 00:06:46,833 166 00:06:46,833 --> 00:06:49,000 it could have been more. 167 00:06:49,000 --> 00:06:52,000 Maybe I shouldn't even use the word 
distinct. Maybe I should say suppose 168 00:06:52,000 --> 00:06:54,000 n can be factored 
in two ways. okay? 169 00:06:54,000 --> 00:06:56,566 And I'm going to prove that they’re the same. That's what's going to happen. 170 00:06:56,566 --> 00:06:58,266 171 00:06:58,266 --> 00:07:00,000 So let's write n 
as a product of 172 00:07:00,000 --> 00:07:04,000 primes p1 up to p k, and 
as primes q1 up to q m. 173 00:07:04,000 --> 00:07:06,000 174 00:07:06,000 --> 00:07:08,800 Again, all these numbers are 
prime. I don't know if k equals m. 175 00:07:08,800 --> 00:07:10,866 I'll try to figure that out 
as I go through this. 176 00:07:10,866 --> 00:07:11,733 177 00:07:11,733 --> 00:07:13,700 But that's the 
idea here, okay? 178 00:07:13,700 --> 00:07:14,833 179 00:07:14,833 --> 00:07:17,033 So suppose that I have 
a number that can be 180 00:07:17,033 --> 00:07:19,133 factored in 
two ways. 181 00:07:19,133 --> 00:07:21,066 Now let's look at the first prime p1. 182 00:07:21,066 --> 00:07:22,933 Well p1 divides 
this product, 183 00:07:22,933 --> 00:07:25,900 and this product is equal to the 
product of primes from q1 up to q m. 184 00:07:25,900 --> 00:07:27,766 185 00:07:27,766 --> 00:07:30,266 So by the Generalized 
Euclid's Lemma 186 00:07:30,266 --> 00:07:33,100 or Generalized Primes and Divisibility, 
however you want to call it, 187 00:07:33,100 --> 00:07:36,000 what do we know? Well p1 divides a product of things, 188 00:07:36,000 --> 00:07:39,633 so p1 must divide some 
element in that product. 189 00:07:39,633 --> 00:07:41,300 So p1 divides some q j. 190 00:07:41,300 --> 00:07:42,633 191 00:07:42,633 --> 00:07:45,633 “By reordering if necessary,” so 
what do I mean by this? Well 192 00:07:45,633 --> 00:07:49,100 q j is just some arbitrary 
element in this product, right? 193 00:07:49,100 --> 00:07:50,166 194 00:07:50,166 --> 00:07:53,766 So let's say q j was something like, 
I don't know, the tenth term, right? 195 00:07:53,766 --> 00:07:55,233 Well... 196 00:07:55,233 --> 00:07:57,133 I'm going to move that 
q j to the first term, 197 00:07:57,133 --> 00:07:59,633 I'm going to move q 1 
over to where q j was. 198 00:07:59,633 --> 00:08:02,766 So what am I doing? I’m 
basically renaming things. 199 00:08:02,766 --> 00:08:06,000 So q j was once called Tom, now 
I'm going to call him Harry, okay? 200 00:08:06,000 --> 00:08:08,000 That's basically what's 
happening here. So 201 00:08:08,000 --> 00:08:10,566 I can assume without 
loss of generality that 202 00:08:10,566 --> 00:08:12,000 p1 must divide q1 203 00:08:12,000 --> 00:08:15,166 because if it wasn’t, then just move 
the terms around, right, reordering. 204 00:08:15,166 --> 00:08:17,566 That's the reordering part 
of the uniqueness, right? 205 00:08:17,566 --> 00:08:19,766 206 00:08:19,766 --> 00:08:22,400 So remember they're unique 
up to reordering. So if 207 00:08:22,400 --> 00:08:25,000 it wasn't the first term, then just 
reorder it so that it was the first term. 208 00:08:25,000 --> 00:08:25,866 209 00:08:25,866 --> 00:08:28,200 Now dividing by 
p1, we can reduce 210 00:08:28,200 --> 00:08:32,466 the number of primes on both sides. We 
can go from p2 to p k and q2 up to q m. 211 00:08:32,466 --> 00:08:33,400 212 00:08:33,400 --> 00:08:36,000 Now hopefully after seeing 
this, you can say, “Oh okay, 213 00:08:36,000 --> 00:08:38,000 well I can just 
keep doing this,” 214 00:08:38,000 --> 00:08:40,633 and the idea is yes 
that's the idea behind 215 00:08:40,633 --> 00:08:42,533 the uniqueness proof of the 
Fundamental Theorem of Arithmetic, 216 00:08:42,533 --> 00:08:46,400 just keep repeating this argument 
until you match up all the primes. 217 00:08:46,400 --> 00:08:48,833 By the end we'll know 
that k must equal m, 218 00:08:48,833 --> 00:08:52,466 and that each prime is equal 
to each other up to reordering. 219 00:08:52,466 --> 00:08:55,333 We might have to keep shuffling 
the primes, but that's okay. 220 00:08:55,333 --> 00:08:56,366 221 00:08:56,366 --> 00:08:59,166 And that's the idea behind the 
Fundamental Theorem of Arithmetic. 222 00:08:59,166 --> 00:09:02,166 So again, it's really 
important… it's a really… 223 00:09:02,166 --> 00:09:04,000 it's just a 
useful result, 224 00:09:04,000 --> 00:09:06,666 that numbers can be factored into primes. 225 00:09:06,666 --> 00:09:10,133 We'll see some applications next week 
and throughout the course we'll see 226 00:09:10,133 --> 00:09:12,733 applications of the Fundamental 
Theorem of Arithmetic pop up. 227 00:09:12,733 --> 00:09:13,966 228 00:09:13,966 --> 00:09:16,433 But that's the main idea. 229 00:09:16,433 --> 00:09:18,333 So where are we going 
now in the course? 230 00:09:18,333 --> 00:09:20,000 Maybe we'll give you a 
little bit of a spoiler alert, 231 00:09:20,000 --> 00:09:22,100 so next week we're 
going to talk about gcd’s. 232 00:09:22,100 --> 00:09:24,466 We're going to kind of enter the number theory part. So this is more of the 233 00:09:24,466 --> 00:09:27,700 proof basics part, first 16 
lectures of this course, 234 00:09:27,700 --> 00:09:29,833 and then from here on out, 
we're going to actually 235 00:09:29,833 --> 00:09:32,000 use this in the context 
of number theory. 236 00:09:32,000 --> 00:09:32,733 237 00:09:32,733 --> 00:09:35,666 And our goal in number theory 
will be to head towards 238 00:09:35,666 --> 00:09:37,133 RSA encryption, 239 00:09:37,133 --> 00:09:41,733 so kind of how we communicate with 
banks online and other industries, 240 00:09:41,733 --> 00:09:42,433 241 00:09:42,433 --> 00:09:46,300 and then from there, 
we'll go into complex 242 00:09:46,300 --> 00:09:50,266 numbers and talk about the algebraic properties of complex numbers. 243 00:09:50,266 --> 00:09:52,000 244 00:09:52,000 --> 00:09:54,600 That's it, I think that's 
all I really have to say. 245 00:09:54,600 --> 00:09:57,100 Again induction 
was the main 246 00:09:57,100 --> 00:10:00,633 topic of this week, 
so focus on that. 247 00:10:00,633 --> 00:10:05,266 That's also, for the January... 248 00:10:05,266 --> 00:10:08,000 well so for the 
winter 2016 offering, 249 00:10:08,000 --> 00:10:11,166 that was also our “midterm 
line”: induction. So 250 00:10:11,166 --> 00:10:13,933 we don't need to know the Fundamental 
Theorem of Arithmetic for our midterm, 251 00:10:13,933 --> 00:10:16,000 but you do need 
to know up to 252 00:10:16,000 --> 00:10:17,333 253 00:10:17,333 --> 00:10:19,600 induction and 
including induction. 254 00:10:19,600 --> 00:10:20,633 255 00:10:20,633 --> 00:10:24,133 So thank you for your time, hopefully 
this helps you and best of luck. 256 00:10:24,133 --> 00:10:24,166