1
00:00:00,000 --> 00:00:03,033
So this is a reminder slide.
So I spoke about this,

2
00:00:03,033 --> 00:00:05,766
I believe in the week 4 video, the 
Fundamental Theorem of Arithmetic,

3
00:00:05,766 --> 00:00:07,533
but I'd like to revisit it at this point.

4
00:00:07,533 --> 00:00:09,633
“Suppose that n greater 
than 1 is an integer,

5
00:00:09,633 --> 00:00:12,366
then n can be factored uniquely
as a product of prime numbers

6
00:00:12,366 --> 00:00:15,000
up to reordering up 
the prime numbers.”

7
00:00:15,000 --> 00:00:18,966
UFT, as the acronym is, is for 
Unique Factorization Theorem. 

8
00:00:18,966 --> 00:00:22,566
Hopefully this will get changed 
to fundamental - or FTA1.

9
00:00:22,566 --> 00:00:26,366
You'll see why the FTA1 is useful,
FTA 2 is going to come later,

10
00:00:26,366 --> 00:00:30,033
but this is the acronym that we're using at 
this moment. We'll probably change it later.

11
00:00:30,033 --> 00:00:32,000


12
00:00:32,000 --> 00:00:34,966
Okay so suppose that n greater than 1 is an
integer, then it can be factored uniquely.

13
00:00:34,966 --> 00:00:37,433
So every number has 
some prime factorization,

14
00:00:37,433 --> 00:00:40,633
as long as the number’s bigger 
than 1. That's the summary of this.

15
00:00:40,633 --> 00:00:43,633
This is something you probably already knew
before. The proof is pretty tricky, as you noticed,

16
00:00:43,633 --> 00:00:45,800
it's very complicated, but…

17
00:00:45,800 --> 00:00:46,533


18
00:00:46,533 --> 00:00:48,000
it's useful. It's very useful.

19
00:00:48,000 --> 00:00:48,666


20
00:00:48,666 --> 00:00:52,000
And it's good to do, it's good practice. It's 
good to do a couple of things that are hard.

21
00:00:52,000 --> 00:00:52,766


22
00:00:52,766 --> 00:00:56,133
Now let's talk about the uses of
this, so why do I care about this?

23
00:00:56,133 --> 00:00:58,066
Well one thing that we can do

24
00:00:58,066 --> 00:00:59,800
is we can now
take a number

25
00:00:59,800 --> 00:01:02,233
and factor it into its
prime factorization.

26
00:01:02,233 --> 00:01:02,966


27
00:01:02,966 --> 00:01:06,233
Why is that important? Well we 
have a couple of theorems now,

28
00:01:06,233 --> 00:01:08,766
talking about divisors and
greatest common divisors,

29
00:01:08,766 --> 00:01:12,000
that come from the prime 
factorization of a number. 

30
00:01:12,000 --> 00:01:12,633


31
00:01:12,633 --> 00:01:15,766
So here I said let n be

32
00:01:15,766 --> 00:01:18,233
equal to this prime factorization.

33
00:01:18,233 --> 00:01:20,000
Now I mentioned…

34
00:01:20,000 --> 00:01:22,233
so in the notes, you can 
actually see a couple 

35
00:01:22,233 --> 00:01:24,400
of ways to write out 
a prime factorization.

36
00:01:24,400 --> 00:01:26,866
This is the one I'm 
choosing for this problem.

37
00:01:26,866 --> 00:01:29,600
So I'm going to 
write n as the product

38
00:01:29,600 --> 00:01:32,533
of distinct prime
numbers: p sub i

39
00:01:32,533 --> 00:01:36,000
to the power of alpha sub i, where 
alpha sub i - these are integers

40
00:01:36,000 --> 00:01:38,000
and they're going to be 
greater than or equal to 1.

41
00:01:38,000 --> 00:01:42,000
So every prime factor, every
prime that appears in this product,

42
00:01:42,000 --> 00:01:44,766
has to appear in the 
prime factorization of n,

43
00:01:44,766 --> 00:01:47,800
and there's also this k. So the k 
value is just your stop index.

44
00:01:47,800 --> 00:01:50,766
So you have k prime factors

45
00:01:50,766 --> 00:01:52,933
and they’re raised to 
certain powers, okay?

46
00:01:52,933 --> 00:01:56,333
So for example, 12 is equal 
to 2 squared, times 3, right?

47
00:01:56,333 --> 00:01:59,233
There would be an example of a 
prime factorization in this form, right?

48
00:01:59,233 --> 00:02:00,266


49
00:02:00,266 --> 00:02:03,600
Then d can be.. then d 
is a positive divisor of n

50
00:02:03,600 --> 00:02:07,333
if and only if a prime factorization 
of d can be given by the following:

51
00:02:07,333 --> 00:02:07,833


52
00:02:07,833 --> 00:02:09,966
so d is equal to this product.

53
00:02:09,966 --> 00:02:11,766
We're now... we have

54
00:02:11,766 --> 00:02:14,133
the same primes, but now 
they’re to the power of delta i,

55
00:02:14,133 --> 00:02:17,900
and these delta i’s are bounded 
between 0 and alpha i.

56
00:02:17,900 --> 00:02:20,933
So notice here that 
the deltas can be 0.

57
00:02:20,933 --> 00:02:24,566
So some prime factors that appear in 
n might not appear in the divisor of n.

58
00:02:24,566 --> 00:02:27,033


59
00:02:27,033 --> 00:02:31,166
And this has to hold and this range 
of this bound has to hold for every i.

60
00:02:31,166 --> 00:02:34,133
So let's just see an example, 
so positive divisors of 63.

61
00:02:34,133 --> 00:02:37,533
So 63 is 3 squared, 
times 7, 9 times 7.

62
00:02:37,533 --> 00:02:40,000
The positive divisors 
are given by what?

63
00:02:40,000 --> 00:02:42,466
They're given by 3 to 
the 0, times 7 to the 0,

64
00:02:42,466 --> 00:02:44,433
so I take no 3’s and no 7’s,

65
00:02:44,433 --> 00:02:46,766
or I take no 3’s and one 7,

66
00:02:46,766 --> 00:02:48,666
or I take one 3 and no 7’s,

67
00:02:48,666 --> 00:02:52,200
or I take one 3 and one 7, 
and so on and so forth.

68
00:02:52,200 --> 00:02:55,266
And if I summarize this list, 
or if I actually simplify this list,

69
00:02:55,266 --> 00:02:58,466
I get 1, 7, 3, 21, 9, and 63.

70
00:02:58,466 --> 00:03:00,600


71
00:03:00,600 --> 00:03:02,300
So again what is this 
saying? So this is saying

72
00:03:02,300 --> 00:03:06,966
positive divisors from a number can be 
given by the prime factorization by taking

73
00:03:06,966 --> 00:03:07,466


74
00:03:07,466 --> 00:03:10,500
subsets of the total number 
of primes that we have.

75
00:03:10,500 --> 00:03:12,233
Just like as follows.

76
00:03:12,233 --> 00:03:13,800
The proof of this

77
00:03:13,800 --> 00:03:17,766
is technical, we didn't do it in class and 
I believe it's not done in the notes.

78
00:03:17,766 --> 00:03:19,700
Maybe it is done in the 
notes I don't actually know.

79
00:03:19,700 --> 00:03:21,033
I didn't do it in my class

80
00:03:21,033 --> 00:03:23,866
It's just technical to make 
the symbols work out,

81
00:03:23,866 --> 00:03:25,933
and this is something that 
we kind of already believe

82
00:03:25,933 --> 00:03:27,833
before this course started, 
so I don't think the

83
00:03:27,833 --> 00:03:30,266
proof is going to add a 
lot to our understanding.

84
00:03:30,266 --> 00:03:31,066


85
00:03:31,066 --> 00:03:33,133
This is Divisors From 
Prime Factorization,

86
00:03:33,133 --> 00:03:36,166
and once we now have 
what kind of divisors…

87
00:03:36,166 --> 00:03:37,800


88
00:03:37,800 --> 00:03:39,766
can occur - by the way
I've just noticed a typo:

89
00:03:39,766 --> 00:03:43,700
“Divisors Form Prime Factorization” should 
be “Divisors From Prime Factorization.”

90
00:03:43,700 --> 00:03:45,833
But anyways, now that we know

91
00:03:45,833 --> 00:03:48,900
the type of divisors 
that can come

92
00:03:48,900 --> 00:03:51,133
from a prime factorization, 
what we can do is we

93
00:03:51,133 --> 00:03:55,600
can now determine when we have 
the greatest common divisor

94
00:03:55,600 --> 00:03:56,700
from prime factorization.

95
00:03:56,700 --> 00:03:58,833
And that's what the 
next theorem says.

96
00:03:58,833 --> 00:04:00,133


97
00:04:00,133 --> 00:04:04,366
So “Suppose we have two integers 
written in their prime factorizations…”

98
00:04:04,366 --> 00:04:08,000
and notice that these two integers, 
all we require is that they are...

99
00:04:08,000 --> 00:04:08,933


100
00:04:08,933 --> 00:04:10,166
positive.

101
00:04:10,166 --> 00:04:13,766
When we allow for the 0 exponents, 
then we can actually get the number 1

102
00:04:13,766 --> 00:04:16,766
by just taking all 0’s as
the exponents, okay?

103
00:04:16,766 --> 00:04:20,000
So this type of prime factorization
gives us a way to write

104
00:04:20,000 --> 00:04:22,700
every single number in 
terms of prime factors.

105
00:04:22,700 --> 00:04:23,366


106
00:04:23,366 --> 00:04:27,000
Notice also that we have two different
numbers but we've used the same

107
00:04:27,000 --> 00:04:29,000
prime factors. How 
can we do that?

108
00:04:29,000 --> 00:04:32,266
And the way to do that is to 
actually just allow for 0 exponents.

109
00:04:32,266 --> 00:04:36,000
So for example I'm going to write 14 
and 15 using the same prime divisors.

110
00:04:36,000 --> 00:04:41,000
Well 14 is 2 to the 1, times 3 to the 
0, times 5 to the 0, times 7 to the 1,

111
00:04:41,000 --> 00:04:41,566


112
00:04:41,566 --> 00:04:46,200
and 15 is 2 to the 0, times 3 to the 
1, times 5 to the 1, times 7 to the 0.

113
00:04:46,200 --> 00:04:46,800


114
00:04:46,800 --> 00:04:48,833
So there I’ve used the 
primes 2, 3, 5, and 7

115
00:04:48,833 --> 00:04:50,900
to write those two numbers 
in their prime factorization.

116
00:04:50,900 --> 00:04:53,066
So don't let the 
notation fool you,

117
00:04:53,066 --> 00:04:56,500
don't let the k’s fool you. 
They can have 0 - like

118
00:04:56,500 --> 00:04:59,500
some of the primes might
not contribute to a and b.

119
00:04:59,500 --> 00:05:03,000
So again so “…if a and b are 
written in the prime factorizations,

120
00:05:03,000 --> 00:05:05,500
then the gcd of a and 
b is this product,

121
00:05:05,500 --> 00:05:07,966
where the only thing that 
we have to define is this m i,

122
00:05:07,966 --> 00:05:10,833
and m i is the minimum 
of alpha i and beta i”.

123
00:05:10,833 --> 00:05:11,866


124
00:05:11,866 --> 00:05:14,866
So a prime factorization so…

125
00:05:14,866 --> 00:05:17,466
again we knew from the 
previous theorem what

126
00:05:17,466 --> 00:05:19,166
the divisors of a and b are,

127
00:05:19,166 --> 00:05:24,000
so the greatest common divisor 
involves the largest possible exponent

128
00:05:24,000 --> 00:05:28,166
in the common divisors, and that value 
is going to be given by the minimum

129
00:05:28,166 --> 00:05:32,266
of the primes appearing in a and b.

130
00:05:32,266 --> 00:05:34,333
So let's just see a 
concrete example. Again this

131
00:05:34,333 --> 00:05:38,300
is a lot of abstract notation, but 
the idea is actually pretty simple.

132
00:05:38,300 --> 00:05:40,700
So here we have the gcd 
of 20,000 and 30,000

133
00:05:40,700 --> 00:05:44,400
so that's the gcd of 2 to the 5, 
times 3 to the 0, times 5 to the 4.

134
00:05:44,400 --> 00:05:44,966


135
00:05:44,966 --> 00:05:48,733
And the other number is 2 to the 4, 
times 3 to the 1, times 5 to the 4,

136
00:05:48,733 --> 00:05:51,100
so how do I get this
prime factorization? Well

137
00:05:51,100 --> 00:05:53,166
I know that 10,000 divides 
both of these numbers, and

138
00:05:53,166 --> 00:05:55,700
10,000 is 2 to the 
4, times 5 to the 4,

139
00:05:55,700 --> 00:05:57,300
so it's actually not too 
hard to factor these.

140
00:05:57,300 --> 00:06:01,600
Sometimes factoring is really difficult though.
Actually, in general, factoring is very difficult.

141
00:06:01,600 --> 00:06:04,700
But here it's easy, when we have these 
nice forms we can factor no problem.

142
00:06:04,700 --> 00:06:06,066


143
00:06:06,066 --> 00:06:09,000
And now what do we do? Well we're 
going to use our GCDPF that's

144
00:06:09,000 --> 00:06:11,000
the equal sign…

145
00:06:11,000 --> 00:06:12,766
that's the second equal sign here.

146
00:06:12,766 --> 00:06:16,000
What do we get? So we take the 
minimum of the powers of 2,

147
00:06:16,000 --> 00:06:17,700
so we have the 
minimum of 4 and 5

148
00:06:17,700 --> 00:06:20,800
we take the minimum of the powers 
of 3, so minimum of 0 and 1,

149
00:06:20,800 --> 00:06:24,000
and the minimum of the powers 
of 4, the minimum of 4 and 4.

150
00:06:24,000 --> 00:06:27,800
So this term is going to go 
away, because it's 3 to the 0. 

151
00:06:27,800 --> 00:06:31,866
This term becomes 2 to the 4, 
and this term becomes 5 to the 4.

152
00:06:31,866 --> 00:06:33,733
Simplifying that becomes 10,000.

153
00:06:33,733 --> 00:06:35,700


154
00:06:35,700 --> 00:06:37,300
And that's it for GCDPF.

155
00:06:37,300 --> 00:06:40,366
You do this computation, and this is the 
result that you're going to get in the end.

156
00:06:40,366 --> 00:06:41,400


157
00:06:41,400 --> 00:06:45,033
I think it's a very powerful result, but 
you have to be careful when using it,

158
00:06:45,033 --> 00:06:46,699
which is what the next 
slide is going to talk about.