So hi everyone, today our topic is number theory. Let's start with a quick warm-up question. With how many zeros does the product of the first 10 consecutive prime numbers end? So we consider the first 10 consecutive number and this is a question of trailing zeros, the zeros at the end. So we have, in order to make 10 a zero, we need 2 and 5, right? We have to count how many 2's and how many 5's we have in this product. Of course, there's only one 2, that's only even prime numbers, and then also only one 5, right? Because anything else that ends with 5 would not be a prime number. So one of these, so that means it doesn't matter how many, we have only one zero at the end. So the answer is B. Okay, so yeah, last week we did logical reasoning, today we'll do number theory. The topics, these are the topics that we will cover in today's lessons. I figure that we just break them into small sections and we go into the theory when we reach the relevant concepts. So let's start with prime factorizations. Every positive integer has exactly one prime factorization, so you know this theorem very well. And this is another common concept that got used very frequently. Two integers whose only common positive divisor is 1 are called relatively prime or coprime. So for example, 5 and 36, the GCD to 1, so these are relative prime. You can even make 25, right? And then lots of times you actually have to determine if a number is prime or not. We don't have to check for every single divisor of n, we only have to check up to square root of n, right? And we actually can prove that. So for example, if you need to determine whether 1001 is a prime number or not, then we know that roughly 2024 is 2 to the 10th, and that means it's a square of 2 to the 5th, right? Which is 32. So we have to go to check all the prime numbers from 2, 3, 5 up to 31 to see if any of these is a divisor of 101. If not, then we can conclude that 101 is a prime number. So that's the order composition, and I strongly recommend you remember all the prime numbers less than 100. Okay, so let's do one question with prime factorizations. There are 4 children of different integer ages under 18. The product of their ages is 882. What is the sum of their ages? So remember, these have to be different, under 18, and the product is 882. Basically, you have to determine these four different numbers. If you have an answer or any questions, send them to us through the chat. There's a lot of good questions in today's lesson, so we should get started here. I just do the param factorization. This one is an even, so we do step by step. It's going to be 2 times 441, and 441 is a big number. It's not divisible by, I don't know, yeah, you can see that divided by 9, but you can also see that it's a little bit over 400. And if you remember, remember we talked about this, what is it, identity, n plus 1 equal to n squared plus 2n plus 1. And if you remember this identity, you can sort of save yourself a bit of computation and realize right away that 441 is actually 21 squared, because that's 20 plus 1 squared. And then we right away can write it as 2 times 3 squared times 7 squared, right? And now our next task, we just have to figure out how to, you know, make four numbers out of it that are different and less than 18. So we have a 7 here, 7, we need one 7, 7 times 3 is 21, so no good, but it has to combine with 2 to make another number that's different from 7, so I have 14, right? And then we're left with 9, 3 and 3, and then we have a 9 here, and we need to get a 1 to make it four different numbers, and of course if you add these up, you have 10 and 21, yeah, so the answer is d to the 31. Of course, if you don't remember this identity, you just do 4 plus 4 plus 1, that's 9, so this number is divisible by 9, and just do one more step to get to this characterization. And that brings us also to the next topic, oh, no, we do LCM first, sorry, before disability rules, so least common multiple and greatest common divisor. In order to find the LCM and GCD of two numbers, you know, small numbers, you can find it right away, for big numbers, we probably have to resort to prime factorizations, so just assume that two numbers a and b, you can, you know, factorize them as p1 to the power e1 all the way to pn to the power en, and same for b, p1 to power f1 to pn over fn. I mean, e1 and f1 can, any of e and f can be zero, right, so we can always, you know, write in this way such that all the bases here are the same, exponents can be one. So when you make, when you find GCD of these two numbers, we just have to take all the bases and the exponent going to be the smaller of the two, right, and multiply them together, and for LCM, we also take each base and the exponent going to be the maximum of the two, and if you look at this formula carefully, you can right away prove that, you know, the product of the two numbers, it's going to equal to, not very good, I'm sorry about this, the product of the two numbers is going to be the product of LCM of the GCD and LCM, right, very nice theorems that you can see right away from the way we construct, we find the GCD and LCM, okay. So let's get to one problem, divisibility rule, so you are familiar with most of this, I don't actually usually use a rule for 7, I think I find much easier to just do long divisions. For 6, we need to divide 2 and 3, for 9 and 3, the sum of the digits have to be multiple of 3 and 9, for 4, the last two digits divisible by 4, like you could have a 1, 2, 3, whatever, 48, so this is divisible by 4, and for 8, we need the last three digits to be divisible by 8, right, so 1, 2, 3, and then you need something like 848, so that is divisible by 8. For this one, I think it's a very nice rule, like ABCD, then B plus D minus A plus C must be a multiple of 11 for this number to be a multiple of 11, this rule actually can get used pretty often, okay, so we do that if you need to. Let's do one question with these concepts, Leah, please do this question. Okay, so Tom wrote down several distinct positive integers, none of them greater than 100. Their product was not divisible by 18, so how many numbers at most could he have written? So out of all the positive integers that are less than 100, how many of them can you write down without making a product that's divisible by 18? I'll go ahead and give a few more moments. So this one can be done actually by getting the prime factorization of 18. So this one is 18. It's pretty simple. It's just 2 times 9 or 3 times 6, which ends up being 2 times 3 squared. And what you can do here is if we want as many integers as we possibly can that aren't divisible by 18, we just need as many integers as we possibly can have that aren't divisible by these numbers. So what you can do is you can say, all right, we can pick each of these. So how many integers that are 100 or less aren't divisible by 2? Well, that would just be, there's 50 that are divisible by 2. That's just the 50 even numbers. And then there's 100 total. So 100 minus 50, that means there's 50 numbers that aren't divisible by 2, which is pretty clear. That's the 50 odd numbers, right? And then for 3, there should be 100 total numbers, and then there should be 33 numbers that are divisible by 3. So 3 times 1 through 33, so every number from 3 to 99. So there's 33 different ones, and that means we have 67. And at this point, let's just say, oh, we'll take the bigger one. 67 is the bigger number. So the only thing here is if we do 67, that's basically how many numbers there are that aren't divisible by 3. But we're actually allowed to have 1 because if we have 1 and we still take the product of all of them, you're not going to get 18 because you only have one 3 in it. So actually ends up being 67 plus 1, which is 68 total numbers. And actually, I think there's a different way you could do this, which is just... Actually, no, because the product needs to be divisible by 18. So in order to make sure that the product isn't divisible by 18, you need to find every single one. Basically, you need a product, and you can have as many different values as you can have as long as you don't have one 2 and two 3s. So in this case, we just made sure we didn't have two 3s, and that works. Thank you, Liev. Okay, so algebra with integers. So a lot of times, just like in algebra, you have a problem with number theory. We use the same concept that we generally use in algebra. We have to assign variables to unknowns, right? So, for example, if you need to find some 4-digit numbers that have certain properties, then I just start with the generalized form, a, b, c, d. So if the question is that the number is multiple of 9, then I know that a plus b plus d must be a multiple of 9. Or if it is multiple of 11, then the sum of the numbers in the odd positions minus the sum of the numbers in the even positions must be a multiple of 11. I can set up a bunch of equations like that and use the divisibility rules. And then sometimes, you know, in this case, for example, if we have to solve for equations for x plus 15y, where x and y are reached to be integers only, then we can use the concept of relatively prime, and we can right away, you know, deduce that x must be a multiple of 15, and y is multiple of 4, something like that. So I think divisibility rules are relatively prime and constrained as well. Like we have to bound the variables into a certain range. There are some of the tools that are commonly used to solve problems like this. So let's see. This one is, okay, let's start with a fairly simple one before to get a longer one. 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 we delete the one in the middle. So, you know, just a direct application of what we talked before. We denote the numbers ABC, and we delete B, the middle digit, so it's going to be 9 times AC. So let's just make sure that we have a comfortable manipulation equation like this. Basically, we just have to find all these numbers, pretty much, yeah. If you haven't done many of these questions before, one way you can do that is expand it. A is a hundredth digit, so what is the value of A, B, and C, just expand it. And simplify the equation as much as you can. So I always do the first step and then you can continue. I do it like hundred A plus ten B. Let's see. You don't always have to do it this way, but this is like one very common way to tackle these kind of questions, like this, and which is like, this one is 90 A, that's C, so now we simplify as much as we can, we cross out 90 A here, then you have a 10 A, and then we have a 10 B, and instead of bringing C to this side, this is 9 C. I mean, usually we keep the coefficients of each digit to be positive integers, because that's sort of easier to, you know, if you need to use inequality, so I keep it as, 10 A, is it equal to 9 C. Yeah, please correct me anytime I make mistake, Leah. So is that, so 10 A plus 10 B equal to 9 C? Yeah. Yeah, that's okay, right? And then you, remember, after we simplify, we have to use, is that? It should be 8 C, because you get the C from the left side, sorry. Oh, that's why, I thought like, yes, thank you. Yeah, so make sure you be careful, it's 8 C. So it's 10 A plus B, after we simplify as much as we can, we have equal to 8 C, right? So we simplify even more, we usually want to write each side as a product instead of the sum, because that's when we can use the disability rule, so it's going to be 5 A plus B equal to 4 C. So I will give you one more minute to see if you can figure it out after we, you know, get to this step. If you have an answer, just send it to me through the chat. So this one, we know that 4c, right? 4c has to be a multiple of 5, right? It's divisible by 5. I just use this shorthand notation. 4c is multiple of 5. And remember about relatively prime, because 4 and 5, these are relatively prime, the GCD equal to 1. Also, it's just you have the shorthand notation. Then from here, there's only one way to satisfy this equation that c must be a multiple of 5, right? So that is used to be 0. And now we use a constraint. We know that c has to be a digit, so it can be only from 0 to 9. So c can only have two choices, c equal to 0 or c equal to 5. But if c equal to 0, then right away, a and b has to be 0. So that's not allowed. So c equal to 5. And then you plug it back into this equation. You have a plus b is equal to 4, right? Because c equal to 5, 4. And then remember, a cannot be 0. So a is going to be 1 and b going to be 3. This is a. This is b. Or you can do 2, 2. You can do 3, 1. And you can do 4, 0, because b can be 0. And then from here, you know that there are four such numbers. So this is kind of your question number 14, four points. But it really invokes everything that we talked about before in solving these kind of questions. Any questions or any comments, anything, just send it through the chat. Then we're going to go to the next one, kind of more involved. So let's see if we can do 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 question number 30, I mean, fairly recently, 2020. So eight consecutive three positive integers, each of them is divisible by its last digit. I mean, we basically just have to figure out these numbers. So I take this long question. So take your time. Remember, we are in the topic of using LCM, GDC, and divisibility rules. This is a long question and, you know, it could be scary in the exam because I've had to check like so many numbers, and divided by the, and each number is divided by its last digit, right? So, later you see maybe there's a quicker solution, but this is what I would do in the exam is just a list down all the three digit positive integers. And then we don't know, I mean, there are 10 of them, right? But of course we can cancel out this right away because nothing is divisible by zero. So, this first number is discarded. We still have nine numbers. We don't know whether it's going to bump from 1 to 8 or from 2 to 9, right? So, since we don't know, we just, you know, focus on what we definitely know, right? Definitely these seven numbers in the middle, they have to be divisible by the last digits of each number, right? So, maybe focus on that to see what we can do. Recall the divisibility rules to see what we can do with these seven numbers. And among this number, we see we focus on the easy one first, right? AB2 is definitely divisible by 2, regardless of A and B. So this one, we can put a checkmark on it. AB5 as well, because the last digit is 5, so it's divisible by 5. So this one is also taken care of. And then, let's do this one. AB3 is divisible by 3, so the sums of the digits must be multiple of 3. And that means A plus B, right, for this one, A plus B must be a multiple of 3. So that would be this number. This one, B4, must be divisible by 4, so that means B has to be even, right? So B even. I don't know what to do. I just check one by one and, you know, apply the divisibility rule. And what about this one, AB6? Divisible by 6, that means it must be multiple of 2 and 3. It's even, so that's good. And because A plus B is multiple of 3, then AB6 is also multiple of 3, so we don't need any additional conditions for A and B. This one is also taken care of, right? What about the next one? So this one, this one, I would not apply the rule. I don't even know how to apply the rule for divisible by 7. So I just expand it, right? For this number, you can do AB7, you can write it as 100A plus 10B plus 7. But in this case, this is actually not the best way to expand this number. We're going to expand it using this form. It's going to be 10 times AB, AB as just like two-digit numbers, and plus 7, right? So 10AB plus 7, this must be a multiple of 7, and we know that 7 is made up of 7, and we know that 10 and 7, these two numbers are what we call them relatively prime, right? So that means the number AB, this two-digit number AB must be a multiple of 7. Yeah, so I just do one by one, right? So that will take care of this, and this one, you know, the rule is that the number itself, three-digit has a multiple of 8, so I just leave it for now because I don't know how to proceed. Okay, so I give you one more minute to see if we have these three conditions. Can we find out what A and B are? Yeah, so everything is taken care of except for this one. So this one, by the way, is always divisible by one. Just one more minute to see if you can solve it and send me the answer. Oh, okay. Okay, I realize that the same thing over here, if we kind of follow this path, we're going to list out all two-digit numbers as multiple of seven and find among them which number is divided by three, right? But as similar to over here, we can also expand it is 10AB plus three. This is multiple of three. And because 10 and three on these numbers are co-prime, then AB must also be a multiple of three, right? So that would be an easier sort of the same thing, but maybe more consistent with what we do over here. So we know that AB is multiple of both three and seven. That means it's multiple of 21, right? And then so we're going to have to, you know, it only boils down to a few choices. It's going to be 21, 42, 63, 84, right? And that would take care of this number because B is even, so all these numbers, I mean, B4 is always multiple of four. Actually, I was incorrect. These are not because B is even, so we're actually only left with 42 and 84. Is that correct? Yeah, just correct me. I made a mistake, 42 and 84, right? So we have to check this condition. We have two numbers, four, two, eight, and eight, four, eight. Which of these two numbers are multiple of eight, right? So you can do long divisions, and we see that four hundred twenty-eight is not multiple of eight. So only this one is multiple of eight. And then we check these eight numbers satisfy what describing the question. AB9, which is eight, four, nine, is not a multiple of nine, right? Because the sum is 21. So that means the eight numbers we are looking for are from AB1 to AB8. It doesn't include AB9. And then the sum of them is going to be eight plus four plus one, which is 13. So this is a very long question, I would say, and you should have to be very proficient with the concept of programs and divisibility rules. But once you've solved this one, then, I mean, after we go through all these painful steps, you can, you know, realize that we maybe didn't have to do all what we did before. We can use a generalized form. If I have ABC, right, then I can use it as 10AB and plus C. And this must be a multiple of C, for C from two to eight, right? And this is taken care of. So 10AB, then you have a 10AB, must be divisible by what? By the LCM of all the numbers from one, two, all the way to eight, right? And you can pick out what numbers are, you know, the most relevant in this LCM. Then you can pick out seven and three and eight, and that, and five, that will take care of all the numbers from one to eight. And you find the LCM of this, which is, I think, exactly 840, 840, because these are co-primes, so eight times four is 40, eight times five, 40, seven is 21, so 840, zero. And then you can just check these few choices. That would, you know, that would be the best, but like in the exam, you know, very few people can, you know, find this right away. And then you can always have the choice of going through one by one. So next one is the number of divisors. So if we are given a number, I mean, many times we're asked to find how many, how many divisors does it have, right? So we have a positive integer eight, and we do the prime factorizations. So how to find the number of positive divisors? I mean, they would be a topic for combinatorics, but I think we can, you know, readily see it from here. So any divisor of A would have the form P1 to power n1 times P2 to the power n2 and all the way to Pn, I'm sorry, not the best choice, maybe Mn, right? And nothing else. All the prime factors has to be go from P1 into Pm. And these exponents can be from zero and cannot be bigger than e, right? So how many choices you have for each m? It goes from zero, one, and all the way to e1, right? That's for m1, and that's why there's e1 plus one choices for this exponent, and similarly e2 plus one for this exponent. And then you just sum up all these because they are independent, so use the product rule and multiply them together. And just understanding where this formula comes from is going to be very helpful in solving questions. So don't just remember, understand where it comes from. And for example, you want to find how many positive divisors of 60 have, we do the prime factorization, collect everything in power here, and we take 2 plus 1, this is 1 plus 1, and 5 plus 1, we have 12 of them. So, and then for that, if you understand this formula, you can also solve question, for example, how many positive divisors of maybe 600, that is a multiple of 4, something like that, because you can pick out, you know, certain numbers, certain prime numbers, and then just focus on the exponent of that particular number. Okay, so let's see, apply it to solve this question. How many positive integers are multiples of 2013 and have exactly 2013 divisors? I think last time you said it's good to to kind of do the prime factorization of which year you are taking the exam, right? So, yeah, 2024. I'm just sort of, you know, repeat what I did in the previous slide. Suppose it's the number ABC are the prime factors. And then this is a formula to calculate the number of divisors of n. Oh, maybe I can probably everyone already figure out this step, but I just, you know, just make sure that we, we know how to factorize 2013 first, right? Because you don't want this step to hold you back. So 2 plus 1 plus 3 is divisible by 3. So you divide by 3 first, you get 3 times 6, 7, 1, right? 6, 7, 1 is a big number, but remember the divisible 2 rule for 11, you see right away the middle number is the sum of the two numbers on both sides. So that is multiple of 11. So you take 6 and then you take 6, 6, 7. So that would be 6 and then 1, 1, 1. It's like you, you know, pull the two numbers apart and put their sum in, in the middle, right? Times 11, of course. So maybe, maybe I would write as 11 times 61. Yes. Yeah. Okay. So make, make sure that we pass the first step, like, from factorize big numbers. And 61 is a problem. So we can stop here. Still are difficult questions. So I give you a few more minutes to figure it out. So after doing that, the next step we could do is that any positive numbers that are multiple of 2013 must contain these prime numbers, 3, 11, and 61. So we call such number n, any multiple of 2013, and I write 3 to the x times 11 to the y and 61 to the power z. And then it can have anything else, it could be maybe 5, you can have a 2 to the a, 5 to the b, and 7 to c, whatever, all the way here. I mean, a, b, c can be 0, right? So even though it doesn't have 5, 2, I'm allowed to write it this way. Just that all the factors of 3 have to be absorbed in this term, there's no 3 or 11 or 61 over here, it can have anything except for these 3 numbers, right? And x and y and z, they have to be at least 1, right? They cannot be, you know, 0. They could be 2, 3, but they have to be at least 1. So that would be a generalized form for any numbers that is a multiple of 2013. And once I have this form of n, I think this is sort of the crucial step, just like in algebra, we have to set up the equations. And once we come to this step, then we can apply our formula, right? Then the number of divisors of n is going to be x plus 1 times y plus 1 times z plus 1, right? And times whatever I have from here, right? I can do that because there's no power of 3 and 11 and 61 over here. Then I get this and then I just call this number whatever, maybe I'd call it m, right? And this number of divisors, as we said, it has to be equal to 2013. But 2013, as we said before, we can only factorize it in the only, you know, their factorization as a sum, as a product of numbers is only this way, 3 times 11 times 61. We don't want a 1 here, right? Because any of these numbers has to be bigger, I mean, at least equal to 2. So 2 and bigger than 2, so that means m here has to be equal to 1, right? And we can have a choice of, for example, x, y, z, we can take it equal to 2 and 10 and 60, right? And in fact, this is the only way such that this product is going to be equal to, you know, 3 times 11 times 61. But we can permutate them, right? Because we, I mean, we can switch the orders of x and y and z. And if you can permutate 3 numbers, you have 6 different permutations for 3 different numbers. So that means x can be 2, y equal to 10, z equal to 60, or x can be 10 and y equal to 2 and z equal to 60. We have, you know, 6 ways to permutate them. And that would be the subject of the lesson on combinatorics, but this is a fairly simple case. So we can list them down and the answer would be 6. So I would say it's only number 22, but I consider this as a difficult question because you have to set up this and make sure there's no power of 3 and 11 and 61 in this product. Let's go to the next topics is another topic that, you know, sometimes you see that decimal infractions. This thing you've seen in lower grades, right? Decimal infractions are 2 different representations of numbers. A rational number is a fraction of 2 integers and we have either terminating integers or repeating, I'm sorry, terminating decimal or repeating decimal. And for terminating, the denominator can only contain powers of 2 and 5, right, and nothing else. If you have anything else except for 2 and 5, that would be a repeating decimal, right, just like here. And, you know, irrational, I don't see a lot, but they are non-repeating decimals, like these numbers are not repeated. So I think that's pretty much for this, but let's see. I have one question here. The number 1 over a thousand and 24, a million, 24,000 is written as a decimal with the smallest possible number of digits. How many digits appear after the decimal point? If there's anything you can send to me. So we know that it has to be finite, right? Because using this 5 is part of the number of digits. And we talked about earlier, it's good to remember powers of 2 and power of 5, 1, 0, 22. If you recall, that is 2 to the 10th. So hope that helps a little bit. So if you have the answer or comments or questions, please send to DF and me through the chat. So you have a, you know, if it takes time to understand what the question means, you can start with an example, right? For example, what does it mean for a fraction? Maybe like 0.125, it has three digits after the decimal point. And, you know, one way you can think of like how to get rid of the decimal point, right? So over here, if we have these numbers, 1 over, it's good to write them as a powers of 2 and 5 and 10. So it's going to be 2 to the 10th times 10 to the third power. And then you're going to be 0. I don't know what it is, but it could be a, b, c, more than that, but like c, y, x, whatever. Maybe just x, for example. And then we have n digits over here. So what does it mean? Right. If we have this, one way we can think of that, that if we multiply, because it's easier to work with integers than with decimal or fractions. So if we multiply both sides to 10 to the power n, right, then we can get rid of the decimal point. And that would be the smallest power of 10. We need to multiply on both sides to turn it into an integer. So we'll talk about divisibility rule and all of that. It works well with integers, right? And I think it's much more pleasant to work with integers than that, than decimal. So in this case, if I multiply both sides by 10 to the nth, and 2 to the 10 times 10 to the third. I don't know what this number here is, a big number on the right, but I know that it is an integer, right? And that makes my life so much easier. Integers, and I know that I just need to find the smallest n such that this fraction is an integer, and I can simplify it as 10 to the power n minus 3 divided 2 to the nth, 2 to the 10th, right? And that, we know that it's going to be 2 to n minus 3 times 5 n minus 3, and then 2 to the 10th, right? So 2 has nothing to do with 5, so we can ignore it. And the smallest n that makes this an integer is n such that n minus 3 is equal to 10. So that means n is equal to 30. So as always, the trick here is to turn it into integers so we can use all these kind of divisibility rules. I mean, this is a, I don't know how you feel about this lesson. There's not many theorems, and the algebra is not complicated, but it's difficult in its own way, right? You have to practice a lot with all these kind of equation with integers only. Yeah, we run out of time, but you can look at past year exams, and there's a lot of questions about number theory. If you register for the exam, then you can get access to past year exam and video solutions, or you need extra practice, just let us know. So for example, I mean, we're running out of time, but like, for example, you can, these are actual questions that you can do it at home. I think it's a pretty nice question. So we have time, that's for your actual practice. And next week, we're going to work on sequences and patterns. Basically, we're going to work at how to arrange different numbers or objects in certain configurations. And for that, we would, I think, use quite a bit of number theory, algebra, reasoning. So looking forward to that. And if you have any questions, you can just send it through the chat.

number theory

trailing zeros

prime numbers

prime factorization

relatively prime

primality

LCM

GCD

divisibility