Number Theory - ARITHMETIC FUNCTIONS Lecture 4 | ISI 2027 | Anirudha Sir | VOS

[00:00:00]Hello everyone, welcome to this video. I hope you're all doing good. Uh again, we'll be continuing with this ISI preparation series. I hope you're following it with all your heart. Um this will be probably the last lecture on number theory arithmetic functions.

[00:00:15]It is not really used that much, but sometimes it is playfully asked, maybe not in UGB but in UGB UGA definitely. Uh in in different forms, especially since we're dealing with multi-choice corrects.

[00:00:32]But today we'll be solving in subjective forms only. We will be understanding what arithmetic functions are, what multiplicative functions are and we will be basing our questions purely on that.

[00:00:44]All right?

[00:00:45]So we'll solve mainly questions dealing with multiplicative functions and you'll understand why it is so important. What is a multiplicative function first of all, if you may ask uh me, then I'll tell you.

[00:01:00]Multiplicative function arithmetic function is first of all, it is dealing with dealing with uh integers, right?

[00:01:12]Arithmetic operations on integers. Now, if it is what what is a multiplicative function?

[00:01:19]Multi plicative function.

[00:01:26]This function is let's say f of n. This is from n to n.

[00:01:32]This is defined such that f of mn equals to f of m into f of n whenever if the gcd of m {comma} n is one. If m and n are coprime then it follows this property. This kind of functions are called multiplicative functions.

[00:01:55]Okay. So what is the first question? Let G be an arithmetical function defined for each n greater than or equal to 1 by this. So, G of n is defined each integer can be, you know, categorized among 0 mod 3, 1 mod 3, 2 mod 3. So, if it is 0 mod 3, it is 1, 1 mod 3, 2, and so on and so forth.

[00:02:21]Okay. So, is this a multiplicative function?

[00:02:27]Huh. So, first of all, the characteristic of a multiplicative function is that since it takes only non-zero values, it takes only values in natural numbers.

[00:02:41]You know, because it is an arithmetical function, that means the domain and codomain both are n only.

[00:02:48]Okay?

[00:02:50]Now, what does that mean? G of n is never zero.

[00:02:53]So, G of n is equal to G of n into 1, which will be equal to G of n into G of 1.

[00:03:01]So, that will imply that G of 1 has to be 1 always.

[00:03:07]If it is multiplicative.

[00:03:10]Yeah? If G is multiplicative.

[00:03:19]Okay?

[00:03:20]So, what what does that mean?

[00:03:23]What is G of 1 but it is equal to two as one is congruent to 1 mod 3, obviously.

[00:03:32]Right? So, that implies G of 1 is 2. So, this immediately tells me that this is not a multiplicative function.

[00:03:44]Got it?

[00:03:45]So, G of 1 for a multiplicative function, another This is another important thing which you can, you know, wave it is that a multiplicative function at one must be equal to.

[00:03:57]Now, if you want to check it in some other way, let's say g of 2 into 3 should be g of 2 into g of 3.

[00:04:07]But what is g of 2?

[00:04:09]What is g of 6?

[00:04:12]Is it equal to g of 2 into g of 3?

[00:04:16]Let's check this. What is g of 6?

[00:04:18]Because it is 0 mod 3, this will be 1.

[00:04:23]What is g of 2? g of 2 is 2 mod 3, so it will be 3.

[00:04:29]And g of 3 is 0 mod 3, so it will be 1.

[00:04:32]So, this is again creating a problem, not possible.

[00:04:38]Right? Therefore, g is not multiplicative.

[00:04:48]Can [snorts] there be multiplicative functions? Definitely, there can be multiplicative functions.

[00:04:53]But, let us assume this also. Let's look at this question.

[00:04:57]Does there exist a multiplicative function such that this happens?

[00:05:02]Now, what is what can we do? This is basically we want to prime factorize these things.

[00:05:08]Why?

[00:05:09]So, let's see. 30 is 6 into 5, so that is 2 into 3 into 5.

[00:05:15]105 is 3 into uh 15 3 [snorts] into 15, is it?

[00:05:23]No, no, no.

[00:05:24]3 into 21.

[00:05:28]No.

[00:05:30]It is 3 into uh 35.

[00:05:36]Ah.

[00:05:37]3 into 35, so 3 into 7 into 5. So, I'm thinking 5 into 21. I don't know, I You messed it up. Okay.

[00:05:47]70 is 7 into 10, so 2 into 5 into 7.

[00:05:51]This is there.

[00:05:52]So, that means f of 2 into f of 3 into f of 5 is 0.

[00:05:59]f of 3 This is the first one.

[00:06:03]Second one, f of 3 into f of 7 into f of 5 is 1.

[00:06:09]Thirdly, f of 2 f of 5 f of 7 is equal to Please note that these two will imply clearly that f of 2 cannot be 0, f of 3 cannot be 0, f of 5 cannot be 0.

[00:06:27]See that?

[00:06:29]So, how can the product be 0?

[00:06:32]How is this possible?

[00:06:34]This is impossible.

[00:06:36]Not possible.

[00:06:40]So, again, f is not a multiplicative function. This implies f is not a multiplicative function.

[00:06:54]Okay?

[00:06:56]That's it.

[00:06:58]Okay, read uh this question. Here, we are already given that f is a multiplicative function, and then we have to prove that another function which is related to f uh Wait a minute.

[00:07:12]Ah.

[00:07:13]is related to f has to be a multiplicative function as well.

[00:07:18]This is This looks like a very simple question, but it's not. It's not as simple as you might think.

[00:07:26]Okay?

[00:07:27]Now, you see, then what can we do about this?

[00:07:32]Right?

[00:07:32]f of kn by f of k f is a multiplicative function. So, when can I write f of kn as f of k into f of n.

[00:07:43]I want to do that, but it's not possible. This is not possible. Because uh k and n need not be uh gcd one.

[00:07:53]Right? k n need not be one.

[00:07:55]This is not necessary.

[00:07:59]Okay. So, what do we do? I'll take factors of k which are related to n.

[00:08:05]I can write k as k can be written as k n into uh k m, I guess. Something something else, basically.

[00:08:20]So, I can write k n k n is the uh part of k which is common with n.

[00:08:40]Right?

[00:08:41]So, basically, what is happening? k m {comma} n is one.

[00:08:46]So, what is happening here?

[00:08:48]I can write And and also k n {comma} k m is one.

[00:08:56]Okay? So, I can write f k n as f of k n into k m into n.

[00:09:04]So, you see that these two have common stuff. So, I'll write it like f of k n into n into k m.

[00:09:13]These two are gcd one. So, I can write this as f of k n n f of k m.

[00:09:23]You understand?

[00:09:25]And what is f of k? f of k also I can write it as f of k n into k m.

[00:09:31]Since k n and k m also have one.

[00:09:37]Right?

[00:09:38]Do you understand what I'm trying to do?

[00:09:40]I'm trying to take the common part the part of K which is having something common with N separately and which has nothing to do with N separately as K.

[00:09:54]Now, I'm just separating those two so that I'll have some sort of ease in calculation.

[00:10:01]So, this is K N into F of K N.

[00:10:06]So, now what happens? What is G of N?

[00:10:09]This becomes F of K N N F of K N by F of K N F of K N. Now, you see that we can cancel this out because we're only taking from N to N, which is not written here, but yeah, we're only taking N to N.

[00:10:31]And this can be F of K N N by F of K N.

[00:10:36]So, this is for each N.

[00:10:38]I can figure it out for each N. I can So, for each N we will have part of K which is totally common with N and we'll have part of K which is not at all common with N and the not at all common part is getting canceled out in the numerator and denominator.

[00:10:56]Right? Now, let us assume Now, what do we need to show? We want to show We want to show GCD or rather G of AB is equal to G of A into G of B.

[00:11:13]Right?

[00:11:14]This is what we want to show where uh A {comma} B, the GCD of A {comma} B is given to be 5.

[00:11:21]Now, what is G of A?

[00:11:25]It will be F of KA by F of K.

[00:11:31]If you understood what I did before, I can write k as some k a into k m again.

[00:11:41]So that this will be, you know, k is the part common with a.

[00:11:52]You know, which has common factors with a.

[00:11:54]Nothing common with with a. So what is basically happening again?

[00:12:04]I'll write it I'll repeat it again. So k a {comma} k m is one.

[00:12:10]k m {comma} a is one. So we can write this as k into a by f of k.

[00:12:20]And similarly, I can have g of b as f of k b {comma} uh b by f of k b.

[00:12:36]Right?

[00:12:39]Now what happens with f of you know, g of a b?

[00:12:49]If we have g of a b, then I have to get something like you know, f of k a b by f of k.

[00:13:03]Here what do I do?

[00:13:05]Is that I'll write k as k a k b into k c.

[00:13:12]Something like this. Because a {comma} b are anyways gcd one. So these two are going to be anyways separate. a and b don't have anything in common. So k and k b also won't have anything in common.

[00:13:24]So we don't have any problem in writing like this. So, k a {comma} k b is going to be gcd one.

[00:13:32]k b {comma} k c is going to be gcd one.

[00:13:35]k c {comma} k a is going to be gcd one.

[00:13:38]So, there is no problem at all.

[00:13:40]So, we will [snorts] be easily be able to write k k b k c a b by f of k k b k c All right.

[00:13:53]Uh so, this can be written as uh Oh, There's not much time. So, f of k into a f of k b into b into f of k c divided by f of k f of k b f of k c This will get cancelled and you'll see that this is obviously g of a into g of b.

[00:14:20]It is the same k a k b which we got above.

[00:14:24]The k m is different. The k m is different. Okay?

[00:14:28]So, that is a This is how you have to think when we are talking about multiplicative functions. So, I hope this made sense. All right? So, the next question will be even more mind-blowing if you enjoyed this question.

[00:14:45]You know, if you enjoyed this one. If you have any doubts, please drop that down in the comments.

[00:14:50]Um So, I'm just taking the common part out, non-common part out, and I'm separating them so that the multiplicative part What is important in multiplicative? The gcd one part, right? Wherever the gcd is one, we can separate them.

[00:15:06]The multiplicative property can be utilized. Okay.

[00:15:10]f from n to n be a strictly increasing function such that f of two is equal to two.

[00:15:17]And this is a multiplicative function.

[00:15:20]Wherever they are relatively prime.

[00:15:23]Huh? This is This can be written like this. Show that f is an identity function, that is f of n equal to n for each n greater than or equal to Okay.

[00:15:36]f of n plus one is strictly greater than f of n, right? This is what strictly increasing function mean.

[00:15:44]This means f of n plus one is strictly greater than or equal to f of n plus one, right?

[00:15:52]So, can I prove inductively since f of one is equal to one?

[00:16:00]Can I inductively prove that uh that would that mean f of two is greater than or equal to two?

[00:16:13]And say f of k is greater than or equal to k, that would imply f of k plus one is greater than or equal to f of k plus one.

[00:16:26]This is greater than or equal to k plus one.

[00:16:28]So, can I prove that therefore f of n is greater than or equal to n?

[00:16:35]This is true for all n greater than or equal Is this clear?

[00:16:40]Inductive step. This is a uh So, this is inductive presumption and then this is the inductive step and then yeah, everything is cool.

[00:16:50]Right? Mm.

[00:16:52]Nice. If we get this, I think we can Can we find f of three?

[00:16:59]Mm?

[00:17:00]What is f of three?

[00:17:07]f of two plus one.

[00:17:10]So, it is Okay, it is greater than or equal to three.

[00:17:15]That is fine.

[00:17:17]But what can we do with f of 3? f of Oh, do we have f of 1 equal to 1 by the way? You have to notice that.

[00:17:28]Where did I get this one? f of 1 equal to 1 because uh Oh, oh, oh, I didn't prove it. f of 2 is equal to f of 2 into 1 equal to f of 2 into f of 1. So, f of 1 always has to be 1. You know, in any multiplicative function, you can take it for granted that f of 1 has to be 1.

[00:17:49]Ah, so what do we do with this? What do we do with f of 3?

[00:18:01]Mhm.

[00:18:04]>> [snorts] >> Okay.

[00:18:07]Just a minute. I think there is some Okay, just Okay. So, if we get an inequality from the other side for f of 3.

[00:18:20]Let's say Okay.

[00:18:30]15 is less than 18.

[00:18:35]Or rather 15 is less than 20.

[00:18:39]So, f of 15 is less than f of 20 because f is an increasing function. This will imply f of 3 into f of 5 is less than Okay, rather I would rather write it as 18 less than 20.

[00:19:03]Both should come. I think that is important.

[00:19:06]Because otherwise I cannot separate. So, f of 18 less than f of 20.

[00:19:11]Okay.

[00:19:12]So, what is happening? f of 3 into f of 5 is less than f of 2 into f of 9.

[00:19:21]Right?

[00:19:24]And 9 is less than 10. This will give me that f of 9 is less than f of 2 into f of 5.

[00:19:35]And this will be less than f of 2 square into f of 5. And we know that f of 2 is 4.

[00:19:43]And I can cancel out f of 5.

[00:19:46]So, you have that f of 3 is less than f of 2 square, which is 2 square, which is 4.

[00:19:52]f of 3 is less than 4, and f of 3 is greater than or equal to 3.

[00:19:57]Our initial thing.

[00:20:00]What?

[00:20:01]So, this gives me a strict inequality, which gives me f of 3 is equal to 3 is the only way possible.

[00:20:09]Okay?

[00:20:10]Now, tell me something.

[00:20:12]What is f of 6?

[00:20:16]What is f of 6? This is f of 2 into 3.

[00:20:21]f of 2 into f of 3, which is equal to 6.

[00:20:26]Right? So, f of 3 is equal to 3.

[00:20:29]f of 6 is equal to 6.

[00:20:32]That means between 3 and 6, what happens to the rest of the values?

[00:20:39]Yeah?

[00:20:40]So, do you see that these have to be equally distributed with all the outcome values between 3 and 6 as well?

[00:20:50]Yeah?

[00:20:52]Right? I mean, uh because f is a strictly increasing function.

[00:20:56]So, I'll write it down like this.

[00:20:59]f of 3 has to be strictly less than f of 4 less than f of 5 less than f of 6.

[00:21:07]Right? and these are taking only integer values. This is 3 less than f of 4 less than f of 5 less than 6. So, what are the possible integer values? 4 and 5 only.

[00:21:19]So, f of 4 has to be 4.

[00:21:22]f of 5 has to be 5.

[00:21:25]Okay? The moment I have f of 5 equal to 5, what is f of 10?

[00:21:30]What is f of 10? f of 2 into 5, so it is f of 2 into f of 5. So, this has to be 10 again.

[00:21:39]So, again between f of 5 and f of 10 is has to take, you know, 6 7 8 9.

[00:21:50]These have to be there.

[00:21:52]If this is 5, this is 10.

[00:21:54]So, do you see the pattern?

[00:21:56]This means this has to be f of 9.

[00:21:58]So, f of 9 is equal to 9.

[00:22:03]So, I'll again get f of 18 is equal to 80.

[00:22:07]This implies between 8 and So, again, this will imply f of 17 is equal to 70.

[00:22:14]So, f of 34 is equal to 34.

[00:22:17]And then f of 33 is equal to f of 33 is equal to 33. So, you see the pattern?

[00:22:25]The idea is that if you get one odd number, let's say n is an odd number such that f of n is equal to n.

[00:22:39]Then f of 2n is equal to f of 2 into f of n because always uh always known that 2 {comma} n with an odd number, there is no common divisor with 2.

[00:22:56]So, this is equal to 2n.

[00:22:58]This implies between n f of n less than f of n plus one and so on till f of 2n minus 1 f of 2n.

[00:23:12]This is equal to 2n.

[00:23:14]This is equal to n. The only possible values because it is strictly increasing is that this must have the value 2n minus 1.

[00:23:23]So, by this inductively we can keep on going with these values. I hope you see that this forces our function to be an identity function. This forces our function to be an identity function.

[00:23:42]So, I hope that was clear. I hope you got something to learn from this video.

[00:23:48]And um that's pretty much it.

[00:23:52]Take care. Ta-ta.

[00:23:54]Bye-bye.