the lesson. So last week we did number of logical reasoning, right, so it's a little bit of break from algebra, and today we come back to sort of mainstream machine topic, number theory. So number theory, we mainly deals with properties of integers, right, and definitely we talk about prime numbers and composite numbers. So prime factorizations, right, the fundamental theorem, we have every positive integer has exactly one prime factorization, you guys all know this, and we go, I mean, compared to the lower level, we dig a little bit deeper into the formula. Suppose that I have an integer a, positive integer a, with this as a prime factorization, then a very useful formula that we have is that we can calculate the number of positive divisors of a, which is equal to e1 here, it's the power of the first prime numbers and then prime factors, and we take each of the power exponent plus one and multiply them all together. You can also, this is actually, this formula is quite easy to prove, not just because you want to prove that, but when you truly understand it, it's going to help us solve a lot of problems with more constraints. So we know that any factors of a must have the form p1, n1, all the way to pn, oh, I have to, I should use code, another one, maybe alpha 1, and then alpha n, right, and every divisor of a must have this form, and what are the choice for alpha 1? Alpha 1 actually has choice from 0 and 1 and all the way to e1, so it has e1 plus 1 choices, and that's why, and these are all independent, that's why we multiply them together, and if we truly understand this formula, then it's going to help us to solve a lot more problems when we need to have a constraint on the divisors. For example, the divisor must be a multiple of some number, then we can start with this general formula. And yeah, an example here with 60, after we factorize it, we can find out that 60 has 12 divisors, positive divisors. Another important and useful concept is relatively primes, two numbers, they themselves do not have to be primes, but if they do not have any common positive divisors except for one, then they are called relatively prime or coprimes. And this one, quite a number of problems you have to, you know, identify, determine a quite big number, whether it is a prime number or not, and don't forget this test, the Siebel-era Tostens. In order to test for n, whether it's a prime number or not, we only have to test if n has any factors, any prime factor up to square root of n, right, and that saves us a lot of computations. For example, if you want to determine if 100,001 is a prime or not, then remember that it's roughly square root of 1001 is roughly 32, then we only have to check for whether it has any prime factors up to 31. And then we have least common factors, least common multiples, and greatest common divisors. If we can factorize two numbers in these formulas, then from here we can find the greatest common divisor, right, p1, p1 here, so the common prime factors, and we can take the minimum of the exponents here, e1 and f1, and that's quite intuitive, right, it has to be the minimum of the two, so that is the greatest common divisors, and the same with all other prime factors. And same thing with the least common multiple, we need to take the maximum of these two. And from here, I don't see a lot from that, but quite useful formulas that, I think you know it, but I just type it here. After we have these two formulas, it's actually quite easy to prove that the product of any two numbers is equal to the product of their GCD and LCN, right. You may need to use it, but it's also easy to prove that min of e1, f1 plus max of e1, f1 is actually equal to e1 plus f1. Then we have a lot of rules for divisibility. By now, I think you all remember it by heart, I just want, I don't find the divisible for 7 very helpful, we just need to remember, I think 11 is a very useful one to remember. Let's go to the next slide and see what we can do with 11. So another topic with number theory is algebra with integers, right, we talk about it when we solve equations in which the coefficients are integers and the solutions are constrained to be integers as well. And so, for example, here we have a four-digit number, we denote it as ABCD, if the number is multiple of 9, then we know that the sum of its digits has to be a multiple of 9. If the number is multiple of 11, then we know that the sum of its digits has to be a multiple of 9. If the number is multiple of 11, then we know that we start from left, right, you start from left here, just skip one, just go like this, and sum up all the digits, we can call it in the even or odd position, but from right to left, and subtract the sum of digits in the even positions like this, and that must be a multiple of 11, I find this one super helpful. And we talked earlier about solving variables with restriction, with constraint, for example, for x equal to 15y, and we know that 4 and 15 are relatively prime, that means x has to be a multiple of 15, and y must be a multiple of 4. And another thing is that sometimes we have to deal with problems that require the problems that require the, you know, either the decimal or fractional representations of numbers, these are interchangeable, we should feel comfortable converting between decimal and fractions. I think we talked about it earlier, a rational number is a fraction of two integers, and a rational number can be, it has a finite number of digits in this decimal representation, or the decimal numbers here, the digit has to be repeating, and when the decimal are non-repeating, then we end up with irrational numbers, for example, square root of 2 over here, and a lot of problems with number theory, we have to deal with unit digits and decimals, which we do in this class. Okay, so much for the theory, let's get started, we're going to cover all the topics that we just talked about today in problems. There are four children of different integer ages under 18, the product of their ages is 882, what is the sum of their ages? So we know that they are different integers, and they are smaller than 18, and we know the product is 882, so what is the sum of their ages? May 1st to factorize 881 too, right? Just divide by whatever number is easier and then use the divisibility rule to find more factors. Okay, good. Let's get started. 881, so I know that it's even, so I just divide by 2 first, right? 421. And then once I see 421, I see that the sum of the digits equal to 9, so it must be multiple of 9, so the next step I would just divide this by 9, and that gives me 49. So I know that 882 is equal to 2 times 3 times 3 times 7 times 7, right? I mean, of course, I want to write 3 squared, not 7 squared, but this question actually is easier, just to write out all the factors like this, separately like this, because we need to group them together to make up these four different integers. So we sort of play around with this, and just listing out, I think, I think we have to make it, 1, it's going to be 9, 7, we can have a 7, 9, and 14, because they have to under the ages of 18, so we cannot have a 21, and 6 and 7, so we cannot multiply 3 with 7, 2 with 7 gives us 14, and we like one more number, but, you know, 1 is identity, right? So we can always add 1 over there, just 2, so that we have 4 numbers, which are all different. And if we sum up this, what do we get? 1 plus 7 plus 9 plus 14 is 10, 10, and so 10, and so it's 31. Is it D? Okay. Oh, it's actually 44 and 41, yeah, okay, that's a good point. It's definitely, I find it definitely helpful to remember squares, remember powers of 2, right, power of 3, and then remember 144, you know, 36 times 6, 24, and something like that. Definitely arithmetic helps a lot to get things done in a good amount of time. Okay, good, thank you, so let's go to the next one, I think. Dave's gonna help us with the next two questions. Oh, this is number two first. Okay, so this question is, how many positive integers are multiples of 2013, and have exactly 2013 divisors, including 1 in the number itself? It's, you know, it's not much of a problem statement. It's a multiple of 2013, and it has 2013 divisors. The reason I picked this problem is because actually, we do have slides with teachers with little blurbs of how you could approach solving the problem. And the blurb for this problem was completely wrong, it was really funny. So we all make mistakes, this is a hard problem. So with that in mind, try your best to see what you come up with. There's a lot of corner cases that you have to think about that the blurb completely ignored. But with that in mind, let's go ahead and see what happens. Just relaunch this. David, do you think we should just remind the student the formula I introduced at the beginning? I know it's kind of fast, but yeah, but I don't think it makes sense to dwell on the theory. We better just focus on... We did have a couple late joiners who might have missed that. So if they don't know it, then they have to... So you remember, we need to find out, yeah. So to remember this formula, if you factorize, right, you can explain the data to the late students. Yeah, so this formula is used to know the number of divisors of any number. And you have to use the fact that when you prime factorize a number, every single divisor of the number is a multiple of some of the primes to a certain power, right? If it cannot have any more primes, otherwise it would not be a divisor of the original number. What that means is, if I can just my pen here, every number either has zero powers of p1, because it's just one, you know, it doesn't have it. One power of p1, two powers of p1, or anything up to e1 powers of e1. You can have no powers of e1, you can have all powers of p1, and that's e1 plus 1 possibilities. And then for each of those, you do the same thing for p2. Any divisor of our number can have no p2, it can have all the p2, there's e2 plus 1 ways. And since these are independent, you multiply them. What you get is that if you have this prime factorization, p1 to the e1 times p2 to the e2, and so on, the number of positive divisors is e1 plus 1 times e2 plus 1 all the way to en plus 1. Yes, thank you. Yeah, so you might need to use that formula, and I think it only sticks if we do problems. I do want to say though, you cannot semi-factorize it. You need prime factors, because if you have six, you might say you can have six to the one, or you can have six to the two, right? But you could also have two squared times three, because six splits up, and they don't have to be the same. So you have to factor into primes, because you can't split primes up, and nothing weird happens there. So with that in mind, here's the problem. 2013 divisors, you know the formula now. It's a multiple of 2013, which means you should probably get ahead and try to factorize it. And we'll give it a couple minutes and see how it goes. Okay, I'm going to give just a little bit more time here because we have very few answers. Like I said, this is a hard problem, but hopefully if we have the factorization, or do we not have time? Oh, it's a 61? I see. Yeah. Oh, I'm sorry. Yeah. So, it's like three, right? We know it's three, and then it's 11. Yeah, three, 11, and then 16. Yeah, this is hard. Prime factorization is going to be hard. No, because, yeah, because three and one, and then seven, six and seven, is it seven, one, or eight? You know what I like doing? When I'm on the highway and you're bored and you pass all these signs, what I do is I try to prime factorize the exit numbers before we get to the next one. It's actually fun. You should try it with the time in minutes. That's cool too. Okay, anyway, I think we have to get started. We have about half of us have answered, but they've all been correct, which is absolutely fantastic. This was a hard problem, so I'm really impressed. So, okay, the first step is to know something about what every multiple of 2013 will look like. For that, we need to know 2013 itself, and yes, 2013 equals three times 11, excuse me, three times 11 times 61, right? Which means that any multiple of 2013 will be three to the x something times 11 to the y times 61 to the z times some number, okay, times a bunch of stuff, which is the thing that was conveniently glossed over in the explanation we were offered for this problem. Now the question is, how do we characterize this as having 2013 divisors? Well, we know from the formula that we've got that x plus one times y plus one times z plus one times all this other stuff, all the other numbers that come from here, whatever this is, equals 2013, right? Because that's the number of divisors we have, and this is our formula that we need to use for this problem. Now here's the tricky part. Here's the really important thing you need to notice. We don't know how many prime factors there are in this expression. There could be an infinity of things from here, right? This other number could be as big as we want, it seems. But it turns out that that's actually not true, because since 2013 is three times 11 times 61, and x, y, and z cannot be zero, right, because otherwise it wouldn't be a multiple of 2013, it wouldn't have these factors. These factors over here have to be three, 11, and 61 in some order. They can't be one, or x would be zero. So this is three, this is 11, this is 61, or x plus one is 11, z plus one is three, y plus one is 61, something like that. And because three times 11 times 61 is already 2013, there cannot be anything else. That is the tricky thing about this problem. That's what kind of messed with me a little bit. But it has to be just x plus one times y plus one times z plus one alone equals 2013. That's it. That's all there is to it. And now the problem is very easy, because you have three, 11, and 61 in some order. You just need all the permutations of three numbers, which is three factorial equals six. I hope we've talked about that. But all the different orders of three numbers is six, which means that the answer is D. Now somehow when the slide was being made, what the slide told us is that two times two times two equals six, so six is the answer. I'm not sure about any side of how they came up with that, but there you go. It's a very hard problem. So props to the people who got it. I'm impressed. And feel free to ask questions if there's anything that doesn't make sense, because there are a lot of tricks that you have to see. Well, really, there's one trick, but it's a little bit weird. Yeah. We actually used this twice, the 2013 is very nice question. Maybe we'll talk about permutation in lesson number seven, when we do counting and probabilities. Yeah. Thank you. Let's go to the next one. This is for me? Yes. I think you want to do this one, or I would do this one? It doesn't matter. I'll do this one. I like this one and four. They're both good. All right. Next question. Tom wrote down several distinct positive integers, none of them greater than 100. Their product was not divisible by 18. At most, how many numbers could he have written? So again, this is a frustrating thing in general. I will say this about number theory, that very often the problem statement is so short and it has all these vocabulary words. And that's frustrating. It doesn't seem like there's a lot to get out of. But just think about what it means to not be divisible by 18. Really try to get as much of that as possible and try to restrict your options. Because this is a restrictive problem. We want to figure out what we're not able to do. So yeah, let's do this. Do you want to give them some hint? Oh, I was about to, I was answering another question. This is my, okay, I think we'll actually start anyway, start going through it now. But we have a couple questions about the previous, I might actually go around and say it out loud. It's too complicated for me to explain in chat. Yes, yes, explain to the whole class. So let's begin this problem though first and see if everything else is clarified in the meantime. So the product, so you have a bunch of numbers, right? Each number has a bunch of primes, prime factorizations, blah, blah, blah, blah. And we're multiplying them all together. And that entire product cannot be a multiple of two times three squared, right? That's what 18 is. How can the product of numbers be a multiple of 18? That means that you have a multiple of two somewhere in here. So you have a factor of two and you have two factors of three. If you have two factors of three, that gives you nine. You have one factor of two, that gives you two. And that's not allowed to happen. So there are two ways to make sure that our product is not divisible by 18. Either every number is odd. Let me write this down. So every number odd, number is odd. Because if every number is odd, then, you know, we don't have a multiple of two. And then we're fine. We can have multiples of three. We can have multiples of nine. We can have whatever. Or alternatively, there is only one factor of three in the entire product. Because you can have one factor of three. You just can't have two. Because it can't be a multiple of nine. So if every single number was odd, that would mean that you can have at most 50 numbers, right? 50 is the best you can do. If there's only one factor of three in the entire product, what that means is you have all the numbers that are not multiples of three. And then one number that is a multiple of three. Because you still have a three. I hope that makes sense. There are 33 numbers that are multiples of three. From 1 to 100, right? 3, 6, 9, all the way to 99. Which leaves you with 67 numbers that are not multiples of three. Clearly, if we took all of these numbers and multiplied them, they would still not be a multiple of three. So we're okay. It's not a multiple of 18. But then I could also add the number three to it. Because it still would not be a multiple of nine. Which means that you have a total of 68 numbers that you can write. So either no multiples of two or one multiple of three. So that it's less than one multiple of two and two multiples of three. That's the solution. Thank you, David. I think we're going to use this strategy again when we do counting. See, like complementary counting. That we count what we didn't want to count. And then also, it's an important thing here. To realize that we can break it down into these two cases. Okay, great. Let's do the next one. So we started with two hard problems. Hopefully, it's going to be easier for the next few ones. How many three-digit numbers are there with the properties that the two-digit number obtained by deleting the middle digit is equal to one-ninth of the original three-digit number? So this one, we start with two-digit. Three-digit. And we delete the middle one. So I think we did it before. So I can just get started by we start with a three-digit number. And then we delete the middle one. We get AC. Right? So I think that's probably everyone going to start with this. And great, we are getting there. I will just translate the word problem into an equation, which I think most of you have been doing by this time. So I just translate from here to here and let's try to continue with Algebra to see what we can get out from this equation. half of the class of the answer. So I, I'm just continuing this, I'm just expanding this three digit numbers. Yes, it's just standard expansions, right? And on this side, it's actually nine T-A, we should multiply things out so I can just continue these equations, which is nine T-A plus nine C. So we, it's a very standard procedures. I should expand everything, and I cancel out similar terms as much as possible on both sides. And I would have over here, 10-A plus 10-B, and then equal to eight C, right? I want to have a positive on both sides, easier than having minus eight C on the other side. And then again, we pull out the common factor 10, but then we divide by two because both sides are divisible by two. And then I have this one equal to four C. So this is a very standard procedure. Simplify as much as you can until this point, and what we can do at this point. And remember, this is an integer equations, and the constraints of ABC has to be digits, A has to be different from zero. So at this point, we know that four C is divisible by five, right? And because four and five are relatively prime, so that means C must be a multiple of five, but C is a digit, so that the only one choice for C, C equal to five. But that's not very interesting because that's only one choice that we are asking about how many of them, right? So the real, and so lies in A plus B, if C equal to five, and then A plus B equal to four. Then again, we need to deal with a counting problem. How many choices we have for A and B? A, B would be, I just write an order of A, B, right? So that would be, we just got from maybe four, zero, four, zero, and what else? Three, one, two, two, one, three, right? And C doesn't matter, C can go in the middle, but there's only one choice for C, and this one, which is least about all the possibilities. So actually we got, yeah, we want one correct answer over here. And yeah, kind of interesting why we had, I guess by the most of you got A because maybe at this point you stopped from here, but don't forget that we can, we actually have a multiple choices for A and B. Okay. Another problem with divisibility rules. Let's see this one. Eight consecutive three-digit positive integers have the following property. Each of them is divisible by its last digit. What is the sum of the digits of the smallest of the eight integers? So they are consecutive, three-digit, and then they have the following properties. The divisible by its last digit, and the question, what is the sum, I mean, this is really not important, the question itself, but just information in the question, the problem statement is important. Yes, thank David for the hint. A lot of the time, we don't even know how to get started. I think for this one, I would just write out things so that you can visualize it better and understand what the question means, right? So I just call up these last first digits A, B. A, B, C, and A, B, 6, A, B, 7, A, B, 8, A, B, A, B, 8, A, B, 9. And then now the next thing is I'm going to jump to something. I know maybe C, D depends on how this digit changes. And we go to 0, right? So that's the thing. And now we know that this number has to be divisible by 2. That's what it means. This number has to be divisible by 4. This number must be a multiple of 7. That's what the question means. And at this point, when we write things down, I think we can safely ignore this number, because we do not divide by 0. So we only consider this. That would be the first step. I mean, equivalently, you can just find out what a and b is, right, what's that number. It looks like with lots of constraints, it looks like we can solve for the number explicitly, right? Good, we have an answer coming in. So let's see. Oh, great. Okay, we already started having correct answer. So I will just, you know, continue doing exactly what I did for question number four. I just expand this, right? We can take AB, separate AB from the last digit. So this AB actually is a 10 times AB. So 10 times AB plus two, and also the last digit is two. So I know this one divisible by two. Oh, by the way, we have, these are nine numbers, but we only have eight, I mean, in our problems, only eight of them. So the cutoff, we don't know whether it's here from one to eight or here from two to nine, right? So we only use information that we surely have, which is the seven numbers in the middle. So I only use this. And this one is definitely a multiple of two. This one is 10AB plus three, and 10 is not multiple of three. So I know that AB has to be divisible by three, judging from this, right? And then over here, we have 10AB plus four, a multiple of four, but 10 is only multiple of two. So from here, AB must be a multiple of two as well. Here, it's definitely a multiple of five. So I'm all set. Over here, AB must be a multiple of three, right? Because divisible by six, and 10 is multiple of six. So I pick up another three here, which I already have, so I don't need it. Over here, 10AB plus seven is multiple of seven. So I know that AB must be a multiple of seven as well. So here, 10AB plus eight is multiple of eight. So I know AB must be a multiple of four. Is that correct? It's four. Right, so that is multiple of eight. And I have these four numbers, and AB is a two-digit number. So I know that I have to probably find the LCM of these four numbers, but two is a factor of four, so I can forget about it, and I just need three, four, seven. So if I multiply three, seven, all of these are co-prime with each other, so I just have to multiply them together, and I get 84. And that's actually the only numbers that I have, right? Then, and as long as AB equals 84, I can guarantee these seven numbers are divisible by its last digits. And I want to look for the smallest of these, then for sure, I should choose the cutoff here, right? I should consider the eight numbers from one to eight, and the smallest numbers would be eight, four, one. So the sum of the digits is D. We do have answer, correct answer is D. So again, this question, the little bit of reasoning in the beginning, and it's really test about divisibility rules and how just put things together. We do need LCM here to make the calculation, the least common multiple to make the calculation faster. So we try to cover all different bases. Yes, we do have a prime factorization. We do have multiples and factors. That's a very common in number theory. But sometimes we also have questions with questions like this, with decimals and units digit. The number 1 over 1024,000 is written as a decimal with the smallest possible number of digits. How many digits appear after the decimal point? Yeah, I know the questions are higher points, but I believe that once you get to level 9 and 10, we sort of try to aim for maybe harder questions, but so that we can focus more and go deeper rather than trick questions. Yeah, I hope you don't mind. Yes, so write it in its decimal representation, small it, yeah, I mean, we don't want to have a bunch of zero at the end, so just write in its decimal representation, and the question asks how many digits appear after the decimal point. This is actually a great moment because we were talking about earlier, how it's useful and helpful to memorize your squares and also something else. Yeah. And for those of you who remember this, this is the something else. I'm just, I'm just going to say that. Yeah, it's definitely helpful to, yeah, to learn the arithmetic. Oh, great, we're starting having correct answer. Okay, very good. So one way to think about that, yeah. So what do you mean by decimal? I don't know what it is, but this is a very small number. So it's gonna be 0.0, so I don't know how many zero, right? And might be, I don't know, could be, could not, and then I have a bunch of numbers like this. Maybe I should not claim that it has zero. I would just write zero times, yeah, maybe that's not very precise. I'm just confused if you want, so I just know that this number gonna be 0.01 can be zero, but it just have a bunch of digits like this. And I know it's terminating, right? And why do I know it's terminating? Because we talk about that two times, one zero, two four is two to the 10th. So anything in the numerator, denominator has power of two and five are terminating. So I know there's a 10 n digits over here, and how can I find out what n is? Looks like however you figure out, we just have to change our viewpoint, right? So every time we multiply the number by 10, then we shift the decimal point one to the, one position to the right. So that means the number of decimal point, the number of digits after decimal point is the power of 10 in which, which I have to multiply the number with, so that I can shift this decimal point all the way to the end, right? And that means when I multiply 10 to the nth to this number, I will have an integer, small integers that I can get. So let's do that. We take one over two to the 10, and this one is 10 to the third. And then the whole thing here, I just need to multiply by 10 to the nth power, such that this number is gonna be a integer, right? So that would be easy. 10 to the nth, that's two to the nth, and times five. First I take out, okay, so, because n minus three is this n minus three, so I have two to n minus three, and five to the power of n minus three, right? So I just factorize this, and divide by two to the 10. So five is good, but what I'm interested in here is two to n minus 13, and then times five to n minus three. So this is a key thing. And has to be at least 13 for this product to be an integer, right? So I can shift the decimal point all the way from here to the back. And that means the answer has to be 13, which, yeah, many of you got, so that's great, yeah. Okay, I think that's good. We cover a lot of factorizations. Number, we have one more, but I think we don't have to do that. Let's do these questions to see. Slightly different from what we did before. Also divisions divisor, but I think also a different technique. A divisor of a natural number is called proper if it is greater than one and smaller than the given number. For how many natural numbers is the largest proper divisor 45 times greater than the smallest proper divisors? So the largest greater than 45 times, I mean, it's just 45 times the smallest proper divisor. So, when in doubt, just take an example, right, so for example, take number 60, the proper divisors do not include 1 or 60, that's what it means, we only consider it from 2 to 30, and the question says that the largest proper divisor is 40 times the smallest proper divisors, so how many numbers have that property? I think. Oh, I think, great. Okay, let's get started. We also have only one minute. So, a very, very simple fact but very useful right when we, when we just order the factors of any number from smallest to biggest. Very simple fact but useful that we can make them in pairs right because the products must be equal to the numbers right so here I have a bunch of pairs and usually we have an even number of divisors and even odd numbers and you notice this square very simple fact. So, that means if I had started with number n here I start with one and the next, I call it p, the next divisor, it doesn't have to be prime number but the next divisor is p and I go all the way to like that, the last number n and the number before that I know it must be n over p. Is that correct? Right, n over p. So, the question says that we have n over p is actually equal to what, 45 times p. So, that means n is 45 p squared, right, 45 p squared. And at this point I have to factorise 45 which is 5 times 3 so it's 3 squared times 5 times p squared. And now I know that p is the smallest, this p is the smallest divisor of n except for 1 so from here I know that can p equal to 2? Yes, right, p equal to 2. It has bigger than 1 and over here I know that p can also equal to 3 but it cannot be more than that, right, because otherwise it's not the smallest. So, from here I know that 3 and 5 are actually also divisors of n but p is the smallest of all so p can only be equal to 2 or 3 and that's why I have only 2 numbers and the answer is c. Okay, quite a number of you got some, that's great. Yes, so I think we finished just on time and looking back here, prime decomposition, prime factorisation, the formula to calculate the number of divisors but more importantly understand why that formula comes through so that when the problem changes and with some twist you can still do that. This is useful fact or there's a divisor from small to big, divisibility rules and how to use LCM, GCD to calculate it quickly. What else do you want to add, David? Not really, I think you went over everything. Just remember to, yeah, we talked about this already but try to get in those squares, try to get in those parts of 2, have it try and snap in your head because really when you're doing number theory and you're dealing with integers the most useful thing to have is to be able to manipulate them very quickly.

number theory

prime numbers

composite numbers

fundamental theorem of arithmetic

prime factorization

positive divisors

relatively prime

Sieve of Eratosthenes

greatest common divisor

least common multiple