Main content

## 2003 AIME

Current time:0:00Total duration:10:54

# Sum of factors 2

## Video transcript

In the last video, we
kind of reasoned our way towards finding the sum
of the factors of 27,000. What I want to do in
this video is really just revisit what we did
in the last video, and see if we can come up with a
more generalized way of finding the sum of the
factors of a number. So in the last video,
we started with 27,000. And we figured out that
its prime factorization is 3 to the third, times
2 to the third, times 5 to the third. Or we could have
said 2 the third-- we could have switched
the orders here. And we used that information
to say, well, OK, if this is the prime factorization of
27,000, than any factor-- so, let's say that this is
some factor of 27,000-- it has to be the product
of powers of 3, 2, and 5. So let me make that clear. It has to be 3 to something
times 2 to something else-- they could be the same number--
times 5 to something else. And each of these x, y's, and
z's have to be between 0 and 3, and they could be
equal to 0 or 3. And actually, make it be clear--
they have to be integers. They have to be integers,
where these are integers. Integers. This notation here implies that
you could be any number there, but they have to be
integers in between 0 and 3, including 0 and 3. And just to be clear, we can
just generate arbitrary factors here. We could say, OK,
let's pick zero. It could be 3 to the 0, times
2 to the second power, times 5 to the 1. This will be a factor of 27,000. You could figure out this
is 1, times 4, times 5. This is equal to 20. And you can just
look-- you can just keep taking different
values of x, y, and z to get all of the factor. So essentially, you
have to through all of the different combinations
here and add them up. And that's what we
did in the last video. And to be able to
think through that, I drew a little bit of a grid. I started with powers of 3. So 3 to the 0-- let
me write it here. So you start with 3 to
the 0, 3 to the 1, 3 squared, 3 to the third is 27. And then I had powers
of 2-- 2 to the 0, 2 to the first, 2
squared, 2 squared is 4. And then 2 the third is 8. And here, I was just
looking for the combinations where we're looking at
the powers of 3 and 2 and we're multiplying
it times 5 to the 0. So, we're not even
looking at having a 5 as a factor yet of
all of these combinations. And what we did is we just
took each of these numbers and we multiplied
them by each other. So these would just be
a 1, a 3, a 9, and a 27. I just took 1 times 1
is 1, 3 times 1 is 3. And then you could go
down this row-- 1 times 2 is 2, 3 times 2 is 6. 9 times 2 is 18. You could just keep
going-- 27 times 2 is 54. And you could keep
figuring out all of these. But the shortcut that
we did in the last video is we said, look, you don't
have to figure out all of those. You could just
take this sum over here-- so whatever this is. So 1 plus 3, plus 9, plus 27. We figured out in the
last video it was 40. This is the sum for
this first column. The second sum is just going
to be 2 times this number. So let me make it clear. This is the same
thing as 1 times this. The second column is going
to be 2 times this thing. Because each of these terms
are just being multiplied by 2. So it's 2 times 1, plus
3, plus 9, plus 27. And then the third column
is going to be 4 times. It's going to be 4 times
this business over here. So 4 times-- let me
scroll over-- 4 times 1, plus 3, plus 9, plus 27. And then the fourth
column will be 8 times, and then they'll be plus
8 times all of that stuff. 1 plus 3, plus 9, plus 27. In the last video, I
added them up and got 40, but I'm keeping them
this way on purpose. Because this thing right here,
what I just wrote-- and this is essentially the sums
of all of the combinations where our x's and y's are
integers between 0 and 3, including 0 and 3. And z is 0, because we're not
multiplying any of these by 5. So when we ignore
the 5, the sum here-- and this is exactly what
we did in the last video-- this is exactly
equal to 1 plus 3, plus 9, plus 27, times 1
plus 2, plus 4, plus 8. If you just take
this term right here and distribute it onto
each of these terms you will get this
expression up here. So to find all of the
combinations of the powers of 2 and 3 with not
multiplying things by 5, you, literally, just have
to take the powers of 3 up to the third
power, because that's how many powers-- that's
how high we get when we do the prime factorization
of 27,000-- and sum them up. And then multiply that
times the power of 2 up to the third power. And then, what we did in the
last video, we figured out. OK, this value
right here-- this is when we're only dealing
with 5 to the 0 power. If we want all of
the combinations, we would want this
grid multiplied by 5 to the 0, which is essentially
what this grid already is. And then we would
want to add that to that grid multiplied
by 5 to the first. And then, add that to this
grid multiplied by 5 squared. And then add that
to this whole grid multiplied by 5 to the third. And so this whole grid--
the sum of this whole grid-- is this right over here. Let's just call
this, I don't know. For simplicity, let's
just call this A. So if you really want the sum
of all of the factors of 27,000, you would take A and multiply
it by 5 to the 0, which is 1. And then add that
to A multiplied by 5 squared-- or sorry, multiplied
by 5 to the first, which is 5. And then add that
to A multiplied by 5 squared, which is 25. And then add that
to A multiplied by 5 to the third, which is 125. And of course, you can
factor out an A here. So this is our total sum. This would be the sum of
all the factors of 27,000. But you could factor
and A out here. And so our sum would be A times
1, plus 5, plus 25, plus 125. And we know what A is. A is this thing over here. So the sum of all of the
factors of 27,000-- actually, let me keep this over
here-- is equal to-- and I'll color code it--
it's equal to-- this is A. So A is 1 plus 3,
plus 9, plus 27-- it's not the right
shade of green, but hopefully, you get the
point-- times 1 plus 2, plus 4, plus 8, times 1
plus 5, plus 25, plus 125. So this, essentially,
is giving you a formula for finding the sum
of the factors of a number. You do the prime
factorization of the number. And I'm not doing
in general terms, I'm doing with a
particular case. And I'm doing that
because I think it makes it a little bit
clearer why this works. But our prime
factorization of 27,000 is 3 to the third, times
2 to the third, times 5 to the third. If we really want
to do the sum-- and this is exactly what
we did in the last video, I'm just expressing it slightly
different here-- we just take all of the powers of 3 up
to 3 to the third, add them up. All the powers of 2 up to 2
to the third, add them up. All the powers of 5 up to 5
to the third, add them up. And then, take the product. And we can do that right now. So this is going to be-- so
this first term over here is 40, this term right here, 40
times-- this is 4 plus 8 is 12, plus 3 is 15. Right? 3, yup. 15. And then times--
25 plus 125 is 150. So this is 156. And if you take
the product-- here, actually, let's just do
it just to prove the point that this actually does work. So 40 times 15--
4 times 15 is 60-- so this is going to be 600. So this part right here is
going to be equal to 600. So it's going to boil
down to 600 times 156. So let's just do that. 156-- let's just
multiply it by 6, and then I'll add two
0's to it at the end. So 6 times 6 is 36. 6 times 5 is 30, plus 3 is 33. 6 times 1 is 6, plus 3 is 9. And of course, if we want
to multiply it by 600, we just add two 0's here, and
we get the exact same answer that we got in the last video. So hopefully, you
found that useful. I haven't proven it
in general terms, but you can--
maybe I'll do that, if I feel like doing
a video on that. But you see a general
method for finding the sum of the
factors of a number. Actually, let me
just write that. Let's just do another
problem just real fast. Let's say I had the
number-- I don't know-- let's say we had to find the
sum of the factors of 300. So 300 is 3 times 100,
which is 10 times 10. And that is 2 times
5, times 2, times 5. So 300 is equal to 3 times
2 squared, times 5 squared. That's the prime
factorization of 300. So if we wanted to find the
sum of all of its factors, it would be 3 to
the 0, which is 1, plus 3 to the 1, which is three. We won't go to any
higher powers of 3 here, because that's
the highest power we have in the
prime factorization. So that's dealing with the 3's. Times 2 to the 0,
which is 1, plus 2 to the 1, which is 2,
plus 2 squared-- that's how high we can get, which is 4. And then, times-- you just
do the 5-- times 5 to the 0, which is 1, plus 5 to
the first power, which is 5, plus 5
squared, which is 25. Can't go any higher than
that, because we only go up to two 5's up here
at 5 to the second power. And so this is going to
be 4 times 7, times 31. So this is going
to be 28 times 31. 1 times 28 is 28. Put a 0 down here. 3 times 8 is 24. 3 times 2 is 6, plus 2 is 8,
and then you get 8, 6, and 8. So the sum of all the
factors of 300 is 868. Hopefully, you found
that interesting.