If you are in class 10th, then this is a golden opportunity for you. What is it? It is a golden opportunity because there are many things in class 10th which match the same to same.
Who matches the same to same? from IOQM we can find out the common divisors among all the common divisors, the biggest common divisor will be the greatest common divisor what are A and B? they are two numbers so the greatest common divisor of them bracket is there, means their GCD whose GCD will be equal to?
A plus K times B comma B will be equal to their GCD hello guys, how are you? is everything good? let's go today we are together again and IOQM 2013's We are going to talk about lecture 2 number theory We are going to talk about lecture 2 number theory and what are we going to do in this In this basically what we talked about in last class on divisibility of integers or I should say on divisibility rules we are going to talk about it further and today's topic is the equation of the Common divisor, greatest common divisor and after that least common multiple i.e.
LCM In short we will talk about HCF and LCM and after that we will talk about primes and composites If everything is fine then let's move ahead So today's topic is common divisor Common divisor. Okay, okay, okay. Some students were getting queries. Sir, I am in 10th class.
Sir, how do I proceed? Sir, I am in 9th class. How do I proceed?
So, listen carefully. Listen carefully to this thing. If you are in class 10th, then this is a golden opportunity for you. What is it?
It is a golden opportunity. Because, look, there are many things in class 10th which match the same to same. Which match the same to the same.
in sequence and series you are studying arithmetic progression in 10th class as it is will be useful trigonometry you will study in 10th class as it is will be useful I agree that the level of trigonometry in IUQM is going to be good but you know the basics geometry you have studied in 9th class you will study geometry in 10th class same geometry is going to be useful there if I talk about at a particular point Number theory also has some things that are being used in real numbers chapter and number system which you have studied in class 9th. So these things are going to give us benefits. So it is not like that sir I am in 10th class, sir there are boards too.
How will this be possible? It will be possible. I agree that syllabus is a little tough but syllabus is not like that which you have to study. It doesn't match with the original or boards curriculum It's not like that Some things are similar, so you can do it Let's start Let's talk about common divisor So basically you understand this If I tell you that 2 divides 4 and 2 divides 6 We had done this 2 divides 4 And 2 divides 6 Because if you divide 2 in 4, 2 times And if you divide 2 in 6, 3 times 2 times 2 divides 4, 2 divides 6 So I can say here 2 is a common divisor 2 is a common divisor Common divisor Of both 4 and 6 Ok sir 4 and 6 both have 2 common divisor we can say that so simple point is if a number C divides any two numbers if there is a number C that divides any two numbers A and B then I can say that C divides A and C divides B and in that situation C is known as a common divisor of A and B C will be A and B's common divisor so if I ask you that sir Who are the divisors of 4 and 6? So, in 4, which number is divided?
In 4, 1 is divided In 4, 2 is divided And in 4, 4 is divided Okay, everyone? In 6, which number is divided? In 6, 1, 2, 3 is divided and 6. So, these are the divisors of 6 and 4. So, who are the common divisors of 4 and 6?
1 is the common divisor of both. 2 is the common divisor of both. And there is no other common divisor.
So, this was about common divisors. Let's move on to the next point. Let's talk about the topic of greatest common divisor. What is the greatest common divisor? What is the greatest common divisor?
Basically, the highest common factor of two numbers I had said divisor and factor Both are the same thing But the method is different If you will be asked about things related to factors in olympiad Then its name will be called divisor What will be called? Divisor And greatest common divisor Is something which is similar to HCF Highest common factor If you know HCF then you know GCD also You just have to write GCD to HCF What to write to HCF? GCD Now what does it say? Understand this carefully You know that we can remove the common divisors of two numbers The biggest common divisor in all those common divisors That will be the greatest common divisor You can remove the common divisor of two numbers write common divisors, the greatest common divisor will be and the simple thing is, if a number D divides A and B and is divisible by all the common divisors of A and B D divides A and B and D is divisible by all possible common divisors of A and B all possible common divisors are divisible by D so D is known as the greatest common divisor or in short GCD of A and B or HCF of A and B Highest common factor Hope you understood this Let me tell you If I ask you what are divisors of 6 or 12? In 12, we can divide numbers by 1 I am taking a simple example 12 and 16 we are taking an example of 12 and 16 so I asked you what number of 12 can we divide so 12 can be divisor of 1, 2, 3 3 4 and 5 divided is many jata 6 then 7 9 8 9 9 10 11 8 12 direct pick it to your 12k divisors and take it I see him and a 16 k divisors key list when I 16 make on concern about it about that one 2, 4, 8 and 16 and no other number is divided so who are the common divisors of both?
who are the common divisors of 12 and 16? so both have 1 common divisor then 2 then no 3 then 4 after 4 there is no other common divisor so of these 3 numbers The greatest of the common divisors is the GCD of both numbers or it is the highest common factor Read it like HCF or GCD, things are the same Do you understand the story of GCD? Now let's talk about the next part Basically, the GCD of two numbers like here 12 and 16, how much GCD did you see?
4, how much GCD did you see of both? 4, so basically that 4 can divide 12 and 16 too and that 4 will be always divisible by all possible common factors of both. That means, all the common factors of 12 and 16 from both the common factors, all possible common factors, 4 will be divisible 1 divides 4, 2 common factor 2 divides 4, 4 common factor 4 divides 4 is it clear?
hope so the story is in the hand so GCD of numbers A and B is the unique positive integer D with the following two properties GCD has two special things first, if two numbers have GCD, A and B, then D will divide A and D will divide B and if in any situation a number C comes in front of us, which divides C by A and C by D so C will divide the GCD of both of them if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if if There are some properties of the greatest common divisor very beautiful properties first property if I have two numbers A and B then their GCD will be one or bigger than that what will happen to one or that? it will be bigger than that you understand this, any two numbers of the world like 15 and 17 you will say sir there is no common factor in them they have no common factor So, they don't have any common divisor, so think about it. Their common divisor is always fixed. Who is it?
One. Their common divisor is always fixed. Who is it?
One. Clear? And, you also understand this.
If I put the small bracket on. What did I put on? I put the small bracket.
So, it means that I am talking about GCD of A and B. GCD of A and B GCD of A and B GCD of A and B GCD of A and B GCD of A and B Hope you understand the story till here So GCD of 2 numbers will always be greater than 1 Because 2 numbers common divisor is minimum 1 2 numbers common divisor is 1 Because 1 can divide into all the numbers in the world What can it do in all the numbers in the world? It can divide So basically GCD of 2 numbers will either be greater than 1 or 1 First thing is clear second point is that you have taken out two numbers A and B as GCD then you have taken out the GCD of their modulus you know modulus means magnitude means absolute value what did you take out of both absolute values?
GCD, so what will come to both? same will come if both numbers A and B are negative if both numbers are negative then GCD will be their positive number GCD will be positive number and here the same thing both of them will take modulus and then take out its GCD then also result will be same let's talk about third point if we take out greatest common divisor of any number with zero if we take out greatest common divisor with zero then that number will always come basically absolute value of that number will come regardless to its sign why? understand this carefully If I am asking the greatest common divisor of 15 and 0 So what are the divisors of 15? Think of divisors of 15 If we think of divisors of 15 So divisors of 15 are 1, 3, 5 and 15 These are the 4 numbers which are divisors of 15 And divisors of 0 In 0, which divisor is divided? Divisor of 0 if you divide 0 by 1, it will go if you divide 0 by 2 0 upon 2, always 0 0 upon 3, always 0 0 upon 4, always 0 if you put 15 upon 0, then also 0 is it clear?
so 0 is ready to be divided by any other number than 0 0 is always ready to be divided by any other number than 0 so the simple thing is if we see divisor of 0, then all the real numbers will come non-zero real numbers it is divisible by any other number than 0 so there will be divisors of 0 and 15 in it so when we find any number with 0 GCD So what happens to the second number except for 0? It becomes GCD GCD happens Hope you understood this story well Next point, what does the fourth point say? It says that if I have two numbers A and B Then the greatest common divisor of both A and B Which means the GCD of both A and B What will be the GCD of both A and B? A plus K times B comma B What is the GCD of both of them? ok ok i didn't understand this sir again look understand this small thing lets take simple number you know 12 and 16 both have GCD of 4 both have GCD of 4 4 is divided in 12 and 16 ok sir 4 is divided in 12 and 16 4 is the highest common factor of both what is the highest common factor so if i take 12 If I add or subtract any integer times of 16, then there will be no difference in GCD of both.
Meaning, if I add 16 to 12 and 16 remains as it is, then their GCD will remain the same. How will it be? Let's check it once. 16 times 2 is 32, 32 plus 12 is 44. and 16, if you calculate the highest common factor or greatest common divisor, then it will be 4 Sir, how do you find the greatest common divisor?
So, this is the topic of Euclid's division lemma class 10th Now we will discuss, I will tell you the easiest way to find the greatest common divisor in the market It will be discussed with you, but you must have understood this if you add any number k times to any other number then also the GCD which was coming before and after will be same doing something like this in GCD does not have any impact why are we reading these things? because we have to do something like this to take the question to its solution or answer so you must have understood this story and k should be integer, if we add integer times then it will not make any difference if you add some more times then it will make a difference a and b have two numbers, let's talk about next point a and b have two numbers and you know their GCD so the GCD of a and b and the GCD of b and a will be same a and b and b and a, both have same GCD let's talk about sixth point, what is sixth point? if the GCD of a and b Greatest common divisor GCD, what is it?
G is there. Okay sir, what is the greatest common divisor of both? G is there.
And if D is their common factor, then D will divide A and D will divide B. So D will have to divide G also. Clear? D will divide G also. Same point, last three times, three slides, two times, once this point is coming up again and again.
It is an important point. If the greatest common divisor of A and B is G and D is their common factor, then D will divide A and B, so G will also divide. Clear?
Let's move on. Next point. For any non-zero M, okay? Any non-zero integer you know is M, okay, sir? If you multiply A and B both with M, with whom?
Multiply with M, right? then their GCD will be multiplied by M their GCD will be multiplied by M suppose their GCD was something like this if you multiply M in both numbers then the GCD will be the result we get when we multiply m in this way will be equal to let's talk about next point d divides a, d divides b d is common factor of a and b d is common factor of a and b and d is big if d is big then it is a common factor of a and b if i divide from 0, then if i divide d from both numbers then the greatest common divisor that was coming will also be divided from d whatever you do with both numbers, will happen with its gcd and divide 16 by 2, so this will be 6 and this will be 8 so what is the greatest common divisor of 6 and 8? a number which divides 6 and 8 and is the biggest number of its category so who will divide 6 and 8?
2 so the GCD of these two is 2 so basically if I divide 2 in both the numbers, then in GCD also 2 is divided the impact you will have with both numbers will be same with GCD next thing, if A and B's GCD is G and if I divide both numbers by their GCD that means divide G in A and G in B then what will happen? then the greatest common divisor of both numbers it will disappear and both numbers will be relatively prime for each other what will happen? relatively prime as and when sir, this was 12 and 16's GCD 4 if I divide 12 by 4 and 16 by 4 then how much will come here? here will come 3 and here will come 4 now in 3 and 4, what is left in the name of greatest common divisor?
1 is left and whenever 2 numbers greatest common divisor becomes 1 whenever 2 numbers greatest common divisor becomes 1 then what will we say in that situation? In that situation, we will say that 3 and 4 are relatively prime. What are they?
Relatively prime. Relatively prime or co-prime. What are they?
Co-prime numbers. Okay, sir. Okay.
If you take out two numbers of GCD and divide them by GCD So now the resultant numbers will be 1 and the numbers will be co-prime or relatively and co prime or relatively prime means that the highest common factor of both numbers or greatest common divisor is 1 ok sir, you must have understood the story till here, let's move on to the next point properties of GCD are going on, you will say sir what is this, they are not taking the name to stop, it is GCD, it is not a light topic two questions came in the IOCUM Let's talk about the next point. 10th point is, if GCD of A and B is 1, which means both numbers are relatively prime for each other, both numbers are relatively prime for each other, which means both numbers don't have any common factor other than 1 in the world. So in that situation, A and B are relatively prime for each other, A and C are also relatively prime for each other. A and C are also relatively prime for each other. Also, multiply a and b and c here b is written and here c is written if we multiply both of them then their GCD will be 1 they will be relatively prime is there any common factor in 3 and 4 other than 1?
no their GCD is 1 and is there any common factor in 3 and 7 other than 1? no it is 1 ok sir Okay, so if I keep 3 as it is and multiply 4 and 7, then 4 times 7 will be 28. Tell me, does any common number divide go in these two? Does any common number divide go in these two?
No, it doesn't. So, how much is their BGCD? It is 1. Other than 1, they don't have any common factor. Clear? So, simple thing.
If A and B are co-prime, A and C are also co-prime, then A and B, C will also be co-primes. Let's talk about the next point. Come on. If A is dividing BC, then who is dividing the product of B and C?
A is dividing it. And what is A and B for each other? They are co-prime. Means there is no common factor between A and B.
There is no common factor between A and B. So, Whatever divide we were doing in BC, then B was not dividing. And then what is dividing? A is dividing BC and A and B are co-primes. A cannot divide B, forget it.
So A is dividing C. So A is dividing C. how?
how? how? like 2 divides 3 into 4 so this means if 2 and 3 are co-prime for each other means 2 and 3 how much is the common factor of both?
1 so this is absolutely sure that if this is co-prime with this then definitely this one who has come to divide? the one who has come to divide with this has come to divide 4 we have to understand these things there should be a little idea Let's move on to the next point. 12th point is a very good point. It's a very good point.
Listen carefully. If A and B are both natural numbers. What are they? They belong to natural numbers. They belong to natural numbers.
They belong to natural numbers. And A and B's... gcd1 means both numbers a and b are relatively prime or co-prime numbers so in that situation if someone multiplied a and b and the result is c power k so in that situation if both K and C are natural numbers then for sure both A and B in any situation will have the power of Kth of any prime number how?
understand this carefully let's take an example 4 and 9 both have GCD of 1 4 and 9 have GCD of 1 and if I talk about 4 and 9 are natural numbers if I multiply 4 and 9 so it will be 4 9 36 36 is basically 6 power 2 what is it? 6 power 2 so base is also natural number and power is also natural number base is also natural number and power is also natural number so next thing is think carefully if base is also natural number and power is also natural number then in that situation these two numbers have power 2 these two numbers have power 2 individually so 4 is 2 square and 9 is 3 square then only the product of these two is equal to power 2 of any number So basically the original numbers are Each of A and B is a perfect Keth power. What will be perfect? Keth power.
Ok? Let's talk about 13 points Which point? 13 points.
What does 13 points say? 13 points says that if I have A and B, two numbers, and their GCD is G, then there exist two integers X and Y. Then there exist two integers X and Y. we will exist with this type we will exist with this type that the greatest common divisor I can write it as AX plus BY what do I write?
I can write it in the form of AX plus BY this will always happen I will prove this we will do a question based on this I will prove this to you that if two numbers A and B have GCDG then linear combination of two numbers in the form of linear combination we can represent GCD basically GCD GCD of A,B can be written as can be written as written as the linear combination of linear combination of of A and B we can represent the 2 numbers GCD in the format of linear combination of those 2 numbers what is linear combination? linear combination means Ax plus By linear combination means Ax plus and the special thing is that x and y take integer values and here x and y values are not unique you can get as many values as you want this is possible note in general ax plus by is a multiple of gcd and here x and y are If I talk about 14 points, then 14 points are very important. 14 points and 13 points are the most important. if two numbers are relatively prime means both numbers have gcd is 1 so sir you said that gcd can be represented in the format of linear combination of both numbers so with a there is an integer m and with b there is an integer n and am plus bn equals to gcd which is equal to 1 and for some m and n belongs to z here m and n are What are the names of the integers and which belong to which? From Z This is called Besot's identity Besot's identity And more and more What is the use of Besot's identity?
It has a very strong use Which we will use today and you will get a question related to this in the homework which you will do yourself and send me this was the easiest name looks dangerous Bezos identity but when I took it in use, it was fun let's move on to the next point I hope you understood all these properties of GCD now we will talk about it So we have a question What is the question? The question is Find GCD of 858 and 325 We have to find GCD 858 and 325 And express it in the form of M times 858 plus N times 325 And M and N should belong to integers Which should belong to? From integers First of all If you want to get 2 numbers of GCD So we have a method called Euclid's division algorithm To find the HCF of both numbers, we check 858 and 325 You must be knowing that 325 is a small number and 858 is a big number So what do we do? Please understand this carefully Start dividing from the smaller number to the bigger number Divide 2 times from 325 to 858 Here we have 650 minus 208 208 is left Now it is possible to divide from 325 to 208 further Do not use decimal points Without using decimal point, is it possible to divide 325 by 208?
No. So what should we do? divide 208 by 325 it was not possible to divide by this so we will divide by this we will start the reverse process so divide 208 by 325 you must be understanding 117 now it is not possible to divide 208 by 117 so we will divide 208 by 117 how much is left sir?
As you divide, you will know that 91 will be saved. How much will be saved? 91 will be saved. Now, dividing in 91 is not possible from 117. So, we will divide in 117 from 91. Okay, sir.
One times. How much will be saved? From here, I will have 6 and 2. 26 will be saved. Now, dividing in 91 from 26 is not possible. So, what will we do?
We will divide in 96 from 91. Okay, sir. we will divide from 26 to 3 times, so it will be 78. How much will be left? 13 will be left. 13 will be left.
Now we will divide from 13 to 26. 2 times, right? And how much will be the remainder? 0. And remember, the day when the remainder is 0, the day when the remainder is 0, the day when the divisor was there, the step in which the remainder is 0, the divisor in that step, the answer was hcf so the highest common factor i got here highest common factor or GCD how much it was i got 13 so basically both numbers are 8, 58 and 325 their GCD is 13 there is no problem till here, you can get GCD from this process you can get GCD from two big numbers whose GCD you can't think easily this method is called Euclid's division algorithm and if you want to represent it in this format then you have to write some steps for this I have to write some steps, so shall we write the steps? The first step is that what I have to write in step 1 Step 1 is that I have to write 8.58 as 325 times 2 plus 208 This is the first step Step 2 is that I have to write After that, 325 will come here and 208 will come here.
325 will come here. It was written that 208 times 1 plus in the form of remainder 117. Then what will be step number 3? What does step 3 say after that?
208 will come here. That is equal to 117. times how much? 117 times how much?
1 plus how much? 91 after that what will be step 4? ok why are we writing these steps? we are writing these steps because we will try to make what is written ok so how will step 4 be made? 117 will come here 91 will come here ok sir and multiply by 1 plus how much?
26 what does step 5 say? step 5 says Step 5 says, 91 can be written as 26 times 3 plus 13 Then 26 can be written as 13 times 2 Reminder is 0 And the day when remainder is 0 What will we say? How much is GCD? GCD will be 13 GCD will be 13 because remainder is 0 so the divisor at that time is GCD till here we understood GCD the question is find GCD of both of them and express that GCD in the form of this one in the format of linear combination of both of these numbers we have to represent GCD we have written steps, we don't need it ok sir what we are going to make from steps we are going to represent GCD GCD is written as 13 Now understand carefully, you have to keep the value of 13 Where to keep the value of 13?
Think about it In the first step of making 13 GCD, who will be available as a remainder? we will get the value of 13 from there so if we have to get the value of 13 from here, then we will throw this term there so 26x3 will be minus so the result will be here, instead of 13, it is 91-26x3 from here, I have taken the value of 13 so I threw 26x3 there, so it is minus so 91-26x3, this is the value of 13 you must have understood let's move ahead then what we do? now we have to keep the value of 26 as a remainder now we have to keep the value of 26 so what will be the value of 26?
117 and 91 and if it goes there then it will be minus so 91 as it is is minus instead of 26, we will put the value of 26 and in the multiply we will put 3 instead of 26, we will put the value of 26 and in the multiply we will put 3 as it is so what is the value of 26? 117 this 91 x 1 will be minus so 117 minus 91 x 1 clear? you must have understood till here multiply this 3 91 x 3 then it will be minus and minus plus 91 x 1 x 3 1 x 3 will be 3 now I will ask how many times is 91 here if it is 91 then it is 1 times and here 91 is 3 times so if we club both then it will be 91 times, overall it will be 91 times 4 times minus 117 times 3 times now after this what we will do, see first we write 13 like this there were 2 terms so after 13 we put the value of the remainder we put the value of 26 then we sort it again and make it in 2 terms what we did in 2 terms, we converted it now after converting it in 2 terms again Now what we have to do is, we have to check again that who was the remainder above this?
If we throw 117 times 1 from 208, then it will be minus. So we are going to take out the value of 91 and keep it here. So instead of 91, the value of 91 is multiplied by 4 minus 117 into 3. I have written this as it is, just left blank because I am going to keep the value of 91 and where will I keep that value of 91?
from here, 208-117x1 multiplied by 4, it becomes 208x4-117x4x4-117x3 No problem? you understand the story till here? you must be able to understand it 208 times 4 as it is 117 times 4 and 117 times 3 both are negative here 117 is 4 times here it is 3 times if you add both then how many times it will be? 7 times is it clear?
what to do after this? after this we can do one thing after 91, what was the as a remainder? 117, so add the value of 117 if we will keep the value of 117, then 208 into 4 minus after that what we will do? instead of 117, we will keep blank and in multiply, 7 then what we will do?
what value of 117 we will keep? 325 minus 208 into 1 we will multiply 7, so it will be 208 into 4 minus 325 into 7 minus minus will be plus 208 times 7 no problem, it should not be till here now 208 is 7 times and 208 is 4 times if we club both, then what will be? after clubbing both, it will be 208 times 4 and 7, 11 times so it will be 208 11 times minus 325 times 7 times ok till here there will be no problem now after this let's talk about next after 117 last and the final like remainder who was coming 208, so how much value of 208 will come 858-325x2 so instead of 208 we will put multiplied by 11-325 x7, clear till here you understand this story, you must be able to understand let's put value instead of 208 ok let's put value instead of 208 ok 8.58 minus 325 times 2 So, the value put is If we multiply 11, it will be 8.58 8.58 I am writing something weird 8.58 times 11 minus 325 2 times 11 will be 22 Minus 325 7 times 325 here 22 times, here 7 times, so total will be overall 325 how many times? and 29 times, 325 into 29 so if you observe this, the GCD I was taking that GCD was equal to 13, I kept the value of 13 and solved it so basically this 13, which was GCD I wrote it as 858 times 11 minus 325 times 29 these are the procedures basically we follow these procedures if we to represent both numbers in linear combination format oh good, we did it sir now what?
now you will understand when you will compare that 858, the given we had we had given basically we had given that 858 its m times minus 325 its plus sorry its n times this we had to bring in the form of GCD we had to bring GCD in this form and GCD is in the form above so if you compare, then you will see the value of m is 11 and n is 29 I hope you understood the story that you have taken out the integer value of m and n so that we can write GCD of those two numbers in the form of their linear combination hope so, you must have understood the story one more thing is this value of m and n unique? is this value of m and n unique? no, there can be more such values how to find out? find out one more value 13 is written as 858 x 11- 325 multiplied by 29 in this if I add 858 times 325 and subtract 858 times 325 if I subtract 858 times 325 then wait If I add and subtract both the terms, and take 8.58 as common from both the terms, then 11 and 325 will be added, so it will be 336. If I take 325 as common from both the terms, then I will have 29 and 8.58. So, I will add 29 to 8.58.
8.58 and 2 more scores from that, 8.60 8.60 and 27 will be 8.87 So here 8.87 will be there, clear? So you got one more value of m and n What happened to m and n? You got one more value Similarly, you can get infinite values of m and n if you want But what is its use? Look, if you understood its proof So when I am going to use this in the next question, you will get the story of why this is happening. You will be clear that we can express GCD.
We can express GCD. So let's move ahead in any situation. So if we see its detailed solution, then our GCD came with both numbers 13. And GCD came with both numbers 13 and ahead of that and after that, m and n values are also here, m value is 11 and n value is minus 29 let's move ahead, see what is next we have a nice question Very nice question.
What does it say? If a and b are relatively prime, show that a plus b and a minus b are either relatively prime or their GCD is 2. We are being told that a and b are relatively prime, meaning their GCD is 1. What does it say? Let's write it in the solution first. It said that a and b's GCD is 1, both are relatively prime for each other.
So we have to check and tell that a plus b and a minus b are relatively prime. either they will be relatively prime or the greatest common divisor of both will be 2 we have to check and tell the greatest common divisor of both will be 2 first of all, let the GCD of A plus B and A minus B is D, suppose both of them have GCD D if they are relatively prime then their GCD D will be 1 if D value is 1 then we will say relatively prime if D value is 2 then we will say GCD value is 2 so we have assumed GCD D So, the GCD or HCF always divides both numbers So, I can say D divides A plus B and D divides A minus B Do you remember the last class? You must have remembered it if D is dividing this and D is dividing this, then D will divide both the sum and D will divide both the difference so D will divide this, both the sum, that is D will divide A plus B plus A minus B and D will divide A plus B minus A minus B so, if we divide a plus b by 2a, then we get minus b plus b so, we divide d by 2a and we have and in between so, we divide d by 2a and d by 2b no problem how did we get 2b?
plus a minus a is cut plus b and minus minus is plus b so, we got 2b so d will divide 2a and 2b so d will divide sum and difference so it will imply that d will divide 2a and 2b Do you understand this story? You must have understood it. So D will divide, we have taken two common from both.
So in the bracket, A plus B is left. What is left? A plus B. Okay.
Now after this, I will talk about the next point. What does the next point say? Understand carefully. What does the next point say?
If I move ahead of this, If I move ahead of this, I would have wanted to write these two steps, then also our work was being done. how it was being made, you understand carefully that D was dividing 2a and D was dividing 2b but I know that A and B's highest common factor is 1 so a number which can divide A and B is 1 number How much? It will be 1. Because the highest common factor of both is 1. So, D is dividing A and D is dividing B.
So, this thing will imply that either D is equal to 2 or D is 2. If D is 2, then 2 will divide 2A and 2 will divide 2B. Because 2 will be divided by 2. And apart from that, and d is equal to 1 because because the reason is that a and b are relatively prime for each other so if I think of any other number other than 2 which is d and that number divides a and b and we know that the highest common divisor that divides a and b is 1, they don't have any other common divisor other than 1 so d will be 1 What will be the value of d? 1. If the value of d is 2, then it will divide the 2's in front of 2a and 2b. And if the value of d is 1, then because the highest common factor of a and b is 1, so it will be d1.
There are only two possibilities. So we will write here either d is 1 or d is 2. D is 1 means that both these numbers are relatively prime. D equal to 1 means that a plus b and a minus b are relatively prime.
This means that a plus b and a minus b are relatively prime. And this means that GCD of a plus b and a minus b. is 2 ok sir I have proved both so hence, I hope you have understood this story that what we did in this we were told that A and B are relatively prime both have common factor 1 these two had to be shown as relatively prime or both had to be shown as common factor i.e.
GCD was 2 So what we did is, we assumed that both of them have GCD as D So D will divide this, D will divide this, and will divide both of their sum So D will divide 2a and D will divide 2b So in that situation, D will be 2 or A and B will have some common factor If 2 will be there, then GCD will be 2 If there is a common factor, then what is the highest common factor of both? 1 So D will be 1, clear? So both numbers will be relatively prime I hope you understood this story well Let's see what its printed solution says So its printed solution says something like this Let's talk about it later next question what does it say?
prove that the fraction 21m plus 4 upon 14m plus 3 is irreducible for every natural number m for any natural value of m, this fraction is irreducible do you understand irreducible? do you understand irreducible? irreducible means if 6 by 4 is written or 4 by 6 is written this fraction in this I will divide above 2 and below 2 so it will be 2 by 3 so reducing 4 by 6, what did we write?
2 by 3 reducing 4 by 6 2 by 3 so I will say that this fraction is reducible what is it? it is reducible But we have to prove that this fraction can't be further reduced. It is irreducible. You can't further reduce it. So how will we prove it irreducible?
Think about it. If I take the GCD of both numerator and denominator. What should I do? What should I do in GCD?
Think, think, think, think quickly. So let's talk about what to think about both GCDs. So think, I gave an example 4 by 6, you write 2 by 3 by reducing it. This is reducible.
But this is irreducible. Why is it so? because the numerator and denominator here have GCD of 2 not 1 and here the numerator and denominator of this fraction the numerator and denominator of 2 and 3 the greatest common divisor of them is 1 ok, so you are saying that if the numerator and denominator of any fraction both have greatest common divisor then the greatest common divisor if it is 1 fraction is irreducible what is it?
it is irreducible, we can't further reduce it it is its simplest form okay so sir, can I somehow show that the quantity above and the quantity below which is written in this question those two quantities for each other what is it? it is relatively prime, i.e. how much is its GCD? it is 1, if I show this then is it irreducible?
will it be proved? Yes it will be proved yes it will be proved, this is what you have to do this is what you have to do, so what will we do in this question? understand this carefully what will we do in this question?
I know that in my solution which is written 4 in 21M plus and 14M plus 3 is written in this I will use Bejot's identity what will I use? I will use Bejot's identity in this what is the reason to use Bajor's identity? Bajor's identity says that if there are two numbers A and B if their GCD is 1 then it implies and both sides are implying both sides are implying if this is there then that will also be there and if that is there then this will also be there if the GCD of both numbers is 1 then the linear combination of both numbers If GCD is 1, then you will write GCD in the linear combination format of both numbers And if you write in the linear combination format, then Ax plus By will be equal to 1 And in any situation, if Ax plus By is equal to 1, then you can say that both have GCD is 1 Listen again If A and B are two numbers, then what is the greatest common divisor of both? if both have the greatest common divisor of 1 then the linear combination of both numbers can be equal to 1 and if the linear combination of both numbers is equal to 1 then you can say that the GCD of both numbers will be 1 the greatest common divisor of both numbers will be 1 clear so how to use this? somehow make a combination of numerator and denominator make a combination by which 1 comes in equal to what comes in equal to?
1 comes if 1 comes in equal to what comes in equal to? 1 comes so GCD will be 1 and if GCD is 1 then both numbers will be relatively prime and if both numbers will be relatively prime then it will never be reduced further this will be proved this fraction is irreducible did you understand the story? let's think about it first let's say that d is equal to is GCD of 21M plus 4 and 14M plus 3 okay sir assume that D is the greatest common divisor of both numerator and denominator now we have to bring GCD of 1 what we have to bring GCD of 1 so think first thing you write D will divide 21M plus 4 and D will divide 14M plus 3 will divide both but I know that D if 21m plus 4 which is the numerator and 14m plus 3 purpose is fixed, in equal to I want 1 what I did to get 1 in equal to first m should be deducted, first thing is m should be cancelled when m is cancelled, tell me that in 21 I multiply someone and in 14 I multiply some other integer then add both so both will be 0 so if we multiply 2 in 21M then it will be 42M and if we multiply 14M by minus 3 then it will be minus 42M so we will multiply 21 by 2, it will be 42M and 2 by 4 is 8 and if we multiply 14M by 3, it will be minus 42M so we will get 32M and if we multiply minus 3 with plus 3, then we get minus 9 so the result is minus 1, both will be subtracted 8 minus 9 will be minus 1 so let's put this one in front and that one in back so I will write here that if I multiply 14m plus 3 with 3 and minus 2 times 21m plus 4 then the result will be 1 but So, the one who is sitting above is A and the one who is sitting below is B.
So, 3A-2B is equal to 1. So, the linear expression of A and B is equal to 1. So, this implies that the 14A-2B is equal to 1. and 21M plus 4 their GCD will be 1 that means their greatest common divisor the common divisor of the two largest will be 1 the common divisor of the two largest will be 1 so this implies that there is no common divisor of the numerator and denominator other than 1 there is no common divisor of the numerator and denominator other than 1 and if there is no common divisor of the two So, what will be the simple thing to click? The simple thing to click is that the given fraction is irreducible. Okay sir?
Irreducible. Okay? Hope you understood the question In the question, we used Bajor's identity What did you find? Bajor's identity Bajor's identity was our topic Which we covered here Let's move ahead and see its printed solution So what does its printed solution say?
The same thing that if we make a linear combination And the result is P, then P becomes 1 And their GCD becomes 1 And if GCD becomes 1, then what happens? It becomes irreducible Let's move ahead, same question Prove that this is irreducible For every every positive integer n. For any positive integer value of n, this is irreducible. We have to prove this. So, let's do the first thing in the solution.
First thing, let's assume that GCD of GCD of 12n plus 1 and 30n plus 2 is Let's assume that their GCD is D So it's simple, D will divide in 12n plus 1 and D will divide in 30n plus 2 can divide Think about the next thing Can I make a linear combination Can I make a linear combination Can I make a linear combination with which and GCD1 is proved so I thought if I multiply 5 by 12n plus 1 then it will be 60n plus 5 and more more more so here it is written that 30 is double of 60 so 2 times 30n plus 2 so it will be 60 plus 2004 so if I subtract both then 60n will be deducted from 60n and here was a bracket, so 5 and minus 4, so how much will be left? 1 will be left. So, in that situation, I can say that you wrote D as GCD, I don't have any problem with that.
But, according to Bajor's identity, if their subtraction is 1, then it is a linear combination which is being made with the help of integers, using numerator and denominator and the result is 1, so it implies everything. What does it do? This implies that GCD of these two numbers i.e. 12n plus 1 and 30n plus 2 GCD of these two is 1 greatest common divisor is 1 and because the biggest common factor in them is 1 so it cannot be further reduced so it implies that 12n plus 1 upon 30n plus 2 is irreducible Hope you understood this story Let's see the printed solution The same thing you understood Now this question you can answer in your own homework check whether it is possible to prove it irreducible or not very good question let's move on next point is next point is least common multiple least common multiple means we are talking about LCM you have taken LCM many times of fractions we are talking about LCM what is LCM?
least common multiple of of two integers a and b is the smallest positive integer which is divisible by both a and b like 2 and 3's LCM is asked, so we think of such a number such a small number in which 2 is also divided and 3 is also divided so how much will it be? 6 will be good. If I talk about LCM of 2,4 is the smallest number in which 2 and 4 are divided so that number will be 4 so in 4, 2 and 4 are divided so basically, the least common multiple is that number for two integers which is divisible by the smallest number and we denote it with capital brackets if we put a big bracket above a and b then understand what we are talking about we are talking about LCM we are talking about LCM let's move ahead if you are clear about LCM related to HCF and LCM then we move ahead to the next point what is the next point? This is very familiar IOCUM 2022 Very latest Very new question What is it saying? Find the number of ordered pairs such that If A and B belong, then from 10 to 30 And greatest common divisor of A, B And least common multiple of A, B If whose is A plus b is equal to a plus b ok gcd of b and lcm of ab that is equal to a plus b we have heard that there are two numbers a and b their gcd and the product of LCM is equal to the product of both numbers we have read this, but this seems to be a new thing if the sum of GCD and LCM of two numbers is equal to the sum of both numbers and both numbers belong between 10 to 30 then we have to tell us how many ordered pairs of such numbers exist in the world and how many ordered pairs exist in the world Let's start this question.
Let's talk about the question. Solution. Listen carefully. You know that GCD of A,B into LCM of A,B that is equal to A multiply B and today you have seen one more thing GCD of A,B plus LCM of A,B that is equal to a plus b ok sir you have seen this thing what do you think after seeing this when is this possible when is this possible see when is this possible we will talk about this there are two possibilities first possibility if both the numbers are same what are both the numbers think like if i take first number 10 and second number 10 what should I take for the first number? 10 and what should I take for the second number?
10 so in that situation, what will be the GCD of both numbers? 10 LCM of both numbers is also 10 and both numbers are also 10 10, so 10 plus 10 here also and 10 plus 10 there also so 20 here also, the game is the same if I take 11 11 from both numbers so both numbers GCD is also 11 LCM is also 11 and there also 11 plus 11, both things are equal hello The first case is that the data given by the given system is equal to the sum of both numbers of GCD and LCM So when can this happen? This can happen in two possibilities Here it is written case number 1 If A is equal to B then above condition above condition is fulfilled above condition will be fulfilled if both numbers are equal a and b are equal.
where a and b came from? from these numbers so first thing, how many pairs will be made? first number will be 10, 10 second pair will be 11, 11, third pair will be 12, 12 and last pair will be 30, 30 30, 30 how many pairs are there? 10 to 30 how many numbers are there from 1 to 30?
30 and there is no number from 1 to 9 10 to 30 how many numbers are there from 1 to 9? 9 9 out of 30, how many are left? 21 so 21 pairs of numbers are there how many pairs are there?
21 pairs which one? in which GCD of AB and LCM of AB is equal to BG Clear? You must have understood the first story. Now let's talk about the second story.
Case number 2. Okay, sir. when else is it possible? if both numbers are not same then also is it possible?
yes it is possible but in which situation is it possible? think about it think about it think about it think about it suppose if first number A is Px and second number B is Qx PY means I want to say that both numbers GCD I am assuming the GCD of A and B as P both will be divisible by P so the first number is Px and the second number is Py so this implies that x and y are co-prime both will be relatively prime and they will not have any common factor if they don't have any common factor then if I find the LCM of both numbers LCM of A,B GCD is the greatest common divisor, P will come once and then we will include X and Y, so basically LCM will be PXY Now you have studied that GCD plus LCM should be equal to A plus B Let's put the values, GCD is P, LCM is PXY If we keep A plus B, then PX plus PY will come here Ok, so after that Let's take p common here, here 1 plus xy will be made And here p common will be x plus y, p from p is removed So 1 plus x plus y will come here, so minus x minus y And in product xy that is equal to how much? 0 Then remember factorization, if I factor 1 minus x On taking 1 common and take minus y common Then 1 minus x will be left again So if we take common from both 1-x, then 1-y will be equal to 0. And if the product of two quantities is equal to 0, then at least one of them is 0. So either 1-x is equal to 0, then x is equal to 1. or y equal to 1 either x value will be 1 or y value will be 1 ok ok ok ok are you understanding the story?
that If you keep the value of x as 1, then if the first number is p, then the second number will be p times something. So the first number will have a multiple of the second number. What will be the multiple of that? It will be the second number. If the first number is p, then p times something is b.
If the value of a is p, then the value of b is... P times something will be there. So, the first pair that can be made from here, from this condition, the first pair that will be made will be 10, 20. If I take the first number as 10, then what will be the second number?
It will be 20. It has some multiple. So, we can take 10, 20 and we can also take 20, 10. Why? Because it has said that the value of y will be 1. If you want, you can take y value 1. If you take y value 1, then this number will be p and the one above will be px. There is no multiple of p.
So, 10, 20 and 20, 10 can be like this. Now you will think, sir, we will check the condition. Is 10 and 20 satisfying this condition? Yes, it is. 10 and 20, how much is GCD? 10 and 20, greatest common divisor is 10 and how much is LCM?
LCM is 20, how much is 10 plus 20? 30 and if we sum both numbers, how much is 10 plus 20? 30, did you understand?
you must have understood so 10 is 20, 20 is 10 Will 11 and 22 work? Yes, it will work. Will 22 and 11 work?
Yes, it will work. Take one number and take its multiple. It will work. Can I take 12 and 24?
Yes, I can. Will 24 and 12 also work? Yes, it will. Can I take 13 and 26? Yes, I can.
Will 26 and 13 also work? Yes, it will. Can I take 14 and 28?
Yes, I can. Will 28 and 14 also work? Yes, it will.
and can we take 15 and 30? yes we can take them so 30 and 15 will also come? yes it will come do you understand the story?
it is coming, it is coming it is a question of IQ, not a light question ok after 30, can I take 16? if I take 16, then the multiple of 16 will be 32 it is not available in the set from where A and B belong so we will not take 16 comma 32 ok, is it done? can there be any other possibility?
one more possibility is left, which is 10,30 10 has 30 as the multiple so 10,30 and 30,10 will work is it possible that 11 and 11 has 3 as the multiple, so 33 will come so 33 is not there so this is one more possibility so how many pairs are there here? 2,4,6,8,10,12 and 14 so here came total 14 pairs He was saying how many ordered pairs are coming So 21 pairs here and 14 pairs here So total 35 pairs came 35 pairs came in this world For whom GCD of Asia and LCM of AB both numbers have equal sum and A and B belong to this this was question of IOCUM 2022 it was very nice question I hope you understood we put this condition we took it out from manipulation and we did this condition. Hope you understood this story. Let's move on to printed solution. What is printed solution?
It is same thing. How many pairs will come? 35 pairs.
How many pairs will come? 35 pairs. Hope you understood this solution.
Let's move on to next question. What is question? Pre RMO 2019. Pre RMO 2019 question What does the question say?
Let's talk about it Question says How many ordered pairs of positive integers with a is less than b 100 or greater than a,b or lesser than 1000 satisfy GCD and LCM whose ratio is equal to 1 ratio 495 1 ratio 495 is equal to GCD and LCM So how many pairs of A and B exist in the world? It's the same question, twist is different So the questions are being asked on this topic So we had to think about it Let's talk about it How many ordered pairs of positive integers? A is less than B and this one satisfies this one First of all, you should know that A and B are bigger than 100 and smaller than 1000 and next thing GCD of A,B and LCM of A,B both have ratio of 1 upon 495 both have ratio of 1 by 495 so what we have to do?
we have to tell ordered pairs we have to tell ordered pairs of both numbers first thing we have to assume we have to assume that A and B how much is GCD? If both of them have GCD, what will you assume? Let's take X for both of them Or take A, you can take anything you want Since both of them have A and B, we will not take A for GCD Let's take P for GCD If both of them have GCD, then First number a will be written as px and second number b will be written as py.
What is the benefit of writing like this? Here we will say that x and y are relatively prime. Both are relatively prime. both numbers are relatively prime both numbers are relatively prime means x and y have no other than one common factor so the common factor of a and b the greatest common factor, the greatest common divisor is p nothing else is there so in that situation, the LCM of both numbers who will get the LCM of a and b?
common factor will be p and x and y will also come so LCM will be p, clear the condition we solved there, for that the assumptions will be same ok, the ratio of GCD and LCM is 1 ratio 495 let's keep the value, let's work so instead of GCD I put the value of P and instead of LCM I put the value of PXY that is equal to 1 upon 495 P is also given after cross multiplying or reciprocal you will know that product of x and y is 495 product of x and y is 495 x and y are relatively prime numbers x and y are relatively prime numbers so this is all for today that we will think of values of x and y as which will be of 495 factors and which factors will be there? those factors which have nothing common means there should be no other than one common factor so first of all think of 495 factors think of 495 factors So, in 495, we will divide by 3, 1, 3, 6, 18, 3, 5, 15, 3, 5, 15, 3, 5, 15, 5, 11, 11, 1, clear? So, the product of x and y, we can write 3 to the power of 2, 5 to the power of 1, and 11 to the power of 1. Okay, sir? Okay, no problem till here. Now listen, I thought of making cases.
Suppose if I take value of x as 1, then value of y can be 495. Yes or no? Do you understand this? If I take value of x as 1, then value of y can be 495. Is there any common factor of these two? No. Now let's talk about case 2. What will I take after x value 1?
What will I take after x value 1? What will I take after x value 1? If we give X 3, then what will be left for Y?
Y will have 3, 5 and 11. If you write Y in the format of 3, 5 and 11, then see, one of the common factors of these two... what is the common factor of these two? 3 but I had assumed that x and y are relatively prime both are relatively prime so there should be no other than 1 common factor so you should know that the square of 3 will go to someone or not this 3 part 2 will break and no one will get 1 clear so you should understand that x value can't be 3 so x value is minimum 1 after 1 i can't keep 3, you told me so first we will keep 5 if we give 5 to x then what will be left for y?
3 part 2 into 11, 9 into 11 will be 99 so if we give 5 to x then y will be 99 okay, now let's talk about case 3 what will happen in case 3? if we give x 9 how much we give x? 3 by 2 or 9 so for y we will have 5 and 11 means 55 if we keep 9 for x, then how much will we have for y?
55 will be left and what will happen in case 4? case 4 will be if we give x 11 how much we give x? 11 so how much will be for y? for y we will have 9 x 5 is 45 ok sir ok because i know that from both the numbers, a is smaller than b a should always be smaller than b so you will try that in px and py you will try to keep x smaller than y keep x smaller than y if x is smaller than y then a will also be smaller than b So in all these situations, I kept x smaller and y bigger. Now tell me one thing, if I keep x value more than 11, if I have to keep anything more than 11, then what I have to do is either I multiply 3 square with 11, 99 to x, then x will be bigger than y, so this will not work.
If I multiply 5 with 11 and give 55 to x, then 9 will not be left, so y will be smaller, so this will not work either. And if I give 9, 5, 45 to x, then 11 will be left, so that will also be smaller. So only these 4 cases are possible.
How many cases are possible? Only 4 cases are possible in which x will be small and y will be big. Now what to do after this? After this, let's think. After this, let's think that if x value is 1 and y value is 495, then a value will be 1 into p and b value will be 495 into p.
Okay sir? Okay sir? You know this, right?
You understand till here, right? like here x is equal to 5 and y is equal to 99 so the value of a will be 5p and b will be 99p ok sir, 99p, clear? ok, till here you must be able to understand that a was px and b was py if you add the value of x and y then it is p into 1, p into 495 now the next thing, here a condition was written that is between 100 and 1000 so what if I keep the value of p here that is between 100 and 1000 so the minimum value of p will be 100 because the value of p is the minimum value of p how will we multiply it to become 100? we have to multiply it by 100 how?
by multiplying it by 100 ok, so I have to keep the value of p as 100 so if I keep p as 100, then this will be 100 a will be 100 and b will be 495 x 100 will be 49500 so in this situation where a is 100 in that situation b's value 49500 will be there but I knew that A and B should be between 100 and 1000 so I took the smallest value of P for which A comes between 100 and 1000 for that B is not coming between 100 and 1000 so if I increase the value of P then B will never come between 100 and 1000 means the first case will not give you any solution the first case will not give you any solution no solution from here because whatever value you keep of p whatever value you keep, you have to keep it from your heart and you have to keep it from your heart that both A and B will come in that criteria and then we have to think how many numbers can be like this and we have to answer the number of ordered pairs by counting those ordered pairs so I don't have any value of P here for which both A and B will come in between 100 and 1000 so this case will give us no solution there is no solution after this we will do color change now listen carefully to the next thing if A value is 5P and B value is 99P then you have to do color change so the value of p which i have to keep minimum so that 5p comes in this range between 100 and 1000 So, if I put 20 in P, then 5P will be 5 x 20 will be 100. So, is A in this range? Yes, it is. And if we do 99 x P, then 99 x 20 will be, how much will it be? 0 is as it is, 2 x 9 is 18, 8 is 1, 2 x 9 is 18, 1 is 19. So, it is 980. The minimum value of P, so that A becomes 100, for that P is more than 1000. Means B is more than 1000. B is not coming in this range. So the second case also does not give us any solution.
So the second one also no solution. Why? Because I kept the lowest value of P, so that A becomes equal to 100 between 100 and 1000. So for that, B is directly coming as 1980, i.e. it is a bigger number than 1000. So from here also, no solution will be found. Now let's talk about case number 3. On which we will talk about case number 3? If I take value of X as 9, then A value will be 9P and B value will be 55P.
Okay, now let's think what are the values of P? So in this situation, if I ask you what are the values of P? What should I keep? First of all, 9P.
so what should i multiply? to make it 100 or bigger so 11, 9 is 99 so we need bigger than 100 so we will keep 12 so we will keep 12 so we will make ordered pair of a, b you understand 12 multiplied by 9 is 108 first number 12 multiplied by 55 is 12, 5, 60, 0, 6 12, 5, 60, 6, 66 so first ordered pair is 108, 660 so we multiply by 9 If I keep p value 13 after 12, then 13 x 9 will be 117 And if I do 13 x 55, then 13 x 5 is 65, 5 x 6 is 61, so it will be 751 The number of these numbers is important The ratio of these two numbers, GCD and LCM, one ratio of 495 will definitely happen This is for sure this will be the important thing for next one also ok, then what to do after this? what to do after this?
you will keep increasing the value of p so value of a and b will keep increasing but you have to wait for that value that what i will keep here that B's value should be greater than 1000 because we don't have to take a value greater than 1000 we will count values before that so what should I keep as P's value? that 55P should be greater than 1000 so I am trying random P value in 55 if I multiply 19 95, 9 and 9, 104 it is bigger than 1000, it is 19 so we tried 18, what is 55x18? 18, 5 is 90, 0 is 9, 18, 5 is 90 and 9 is 990 ok, so the day you keep 18 while moving forward, then the last pair will come, which one?
18x9 162 A will be 162 and if you multiply 55 by 18 in B, then it will be 990 after that, if you add any value greater than 18 to p in case number 3 then the value of A will be between 100 and 1000 but the value of B will not be between 100 and 1000 it will be greater than 1000 so in that condition, we will not take the value greater than 18 to p clear? okay, let's talk about the next one what to do after this? first count how many cases are there?
12 to 18, if we talk from 1 to 18 then there would be 18 cases but there are no 11 cases from 1 to 11 so how many are left from 11 to 18? 7 cases are left 7 cases are there, not 7 cases, 7 ordered pairs 7 ordered pairs are made here ok sir? ok Now let's talk about if x value is 11 and y value is 45. If x value is 11 and y value is 45, then what will be the value of a?
11p, right? And what will be the value of b? 45p. Okay, sir? Now let's think what values of p should I keep?
So, from 11, which one should I multiply? That it increases by 100 as soon as I multiply. If I multiply 11 by 9, then 99 comes.
11 will have to be multiplied by 10, minimum. So, I will keep the value of p as 10 first. so after keeping 10, the first ordered pair of a,b will be 110,10 instead of p so 11,10,10 and 45,10,10,4,50 this is the first pair ok we will keep increasing the p value like this after keeping 10, we will keep 11, 12 so on now which last value will I keep by which as soon as we put the value of p here, the value will multiply from 45 and become 1000 so what should I multiply in 45?
see, if we multiply 20 in 45, then we get 900 and if we multiply 22 in 45, then we get 990 so 45 x 23 will never come, at the end, 22 will come and when 22 comes in the last, the last ordered pair will be B is 990 and A is 11x22 242 okay so how many ordered pairs came from here? let's count from here also how many ordered pairs came right? and then we write the answer because 4 E case was possible 1st no solution, 2nd no solution, 7 ordered pairs from here let's see from here how many ordered pairs are coming so if it was 1 to 22 so let's count 22 ordered pairs but it starts from 10 so 9 ordered pairs are missing from 1 to 9 9 out of 22 is 13 ordered pairs so here we have 13 ordered pairs so if you ask me what is the total number of ordered pairs total number of ordered pairs in which this is possible so 7 ordered pairs above and 13 ordered pairs below There are 20 ordered pairs like this. Pairs, okay sir. Okay?
There are 20 ordered pairs. Let's see its printed solution. Let's see what is printed solution.
So, its printed solution is very easy. Very easy. Nothing is written.
Direct answer. 20 ordered pairs are possible. But if we go inside and discuss thoroughly. So, 4 cases are made. No other case is made.
2 out of 4 cases are no solution. 7 out of 2 cases are ordered pairs. Total 20 ordered pairs.
Hope you understood the question. Let's move on to the next question. One more poisonous question is in front of you.
Where is this question from? This question is from IUQM 2022 Okay? IUQM 2022, one more question Now you will say sir, in IUQM 2022 2 questions related to GCD and LCM came Yes, that's what I was saying Number theory, number theory, number theory Number theory of the budget Let M and N be natural numbers, what are M and N? They are natural numbers such that M plus 3N minus 5 That 2 times of LCM of MN minus 11 times of GCD of Mn k is equal to find the maximum possible value of M plus N what we have to find out of M plus N maximum possible value we have to calculate whose?
M and N okay sorry M plus N so we need the maximum value of M plus N so what do we need of M and N? we need the maximum value okay sir okay, let's think let's go to the solution in this question see the same thing M and N we have to talk about GCD and LCM So let GCD of M and N is P So M will be Px and N will be Py In this situation X and Y will be relatively prime Okay sir, there should be no problem till here. There should be no common factor other than 1 in x and y.
Okay sir, what should we do next? So sir, if both have GCD P, then how much will be their LCM? LCM of M and N, how much will it be? P x y will be done. Okay sir, so what should we do?
Put the value, which is given. What is given to me? I am given M plus 3N minus 5, that is equal to 2 times of... 2 times of LCM of M, N minus 11 times minus 11 times GCD of M, N. It is given like this. So, let's put the value.
Instead of M, we put PX. Instead of 3N, we put PY. Okay, sir.
And minus 5, that is equal to 2 times. What did we put instead of LCM? Instead of LCM, we put PXY.
Minus 11, instead of GCD, what did you put? You put P. Okay. Now what to do? P is common among all.
No, no, it is not coming from all. Right? P is not coming from all, Lakshman.
Right? Take all of them there. Okay? So, here PX.
Okay? And in plus, 3PY. Okay, sir?
And 2PX, minus 11P there, so plus 11P. Okay, sir? Plus 2PXY, if it goes there, then minus 2PXY. Okay sir, what is that is equal to? Sir, it is 5. Okay, no problem.
Now you will think what to do next. Do you have any option? Let's think about the option.
Okay sir. So, first of all, P is common among these 4 people. First, remove P. This P is doing a great job. This P has bothered us.
Remove P. We have taken P common from all. As soon as we take P common, here we will have X plus 3Y and minus 2XY and plus 11. Okay. That is equal to 5. Okay.
there can be two things first, this quantity multiplied by this quantity equal to 5 and multiplied by 1 so one thing can happen, p can be equal to 1 p can be equal to 1, means both have highest common factor 1 then the x and y will be the same numbers x and y will be the same numbers in that situation, the whole quantity will be equal to 5k the whole quantity will be equal to 5k so if i make the whole quantity equal to 5k let's write it, so x plus 3y minus 2xy plus 11 that is equal to 5 now someone will say why don't we make p minus 1 so p is gcd, gcd is positive not negative so forget about minus case so x plus 3y minus 2xy that is equal to plus 5 is here minus 5 so 11 minus 5 will be 6 that is equal to 0 okay now see what I did I played a little bit x minus 2xy plus 3y plus 6 that is equal to 0 then I thought what will be the common of these two x will be 1 minus 2y Then what should I take as common from these two? If I take common from these two, how much? 3 If I take common from these two, how much? 3 Let's do one thing, let's keep 6 there only Minus 6, ok sir And if I take 3 common from 3y, then I want that 1 minus 2y should be left here Ok, how will it be left? Absolutely not So let's do one thing Let's multiply 2 on both sides If we multiply 2, then it will be 2x plus 3 is 6y, minus 2 is 4xy and plus 12 is 0. So, 2x with minus 4xy, so 2x common will be 1 minus 2y.
And here plus 6y is written, so here I want minus 3. If I bring here, then as soon as I take common here, then 1-2y will also be here. And bringing here means bringing here also. If you bring here and send there, then minus 12 is already there.
So there is minus 15. How much is minus? 15. Okay. So here, if you take 2x common, then 1-2y will be here.
And here, if you take common here, then 1-2y will be here. Minus 15 is sitting in front. 1-2y common, what will be left? 2x-3 that is equal to minus 15. Clear?
Okay. Give this minus to this bracket. So, it will be 2y-1 and 2x-3 equal to 15. There are two ways to break 15. 5x3 is 15 and 15x1 is 15. Okay. So, 2y-1 if I equal to 1 and 2y-1 is 15. 2x-3 if I do 15, then 1 solution will come and 2y-1 if I do 15 and 2x-3 if I do 1, then 2 solution will come so from here minus 1 will be 1 plus, 2 divided by 2, so y value is 1 ok, and minus 3 will be plus 3, 15 plus 3 18, in 18, how much will be 2 divided by x value 9 ok, x value 9, y value 1 and if we put minus 1 here, then plus 16 will be 2y equal to 16, then y value will be 8 and minus 3 will be plus 3, then 1 plus 3 is 4, 2x equal to 4, then x value will be 2 so if we take gcd as 1, case 1, now case 2 is also remaining if I take gcd as 5, then what will happen? In case 1, we know that if we take gcd as 1, then x value 9 and y value 1, then the first pair of numbers will be a, b.
Because I know that gcd is 1, so x and y will be the numbers. So x9, y1, so the first pair is 9,1 and the second pair is 2,8. So, the sum of both numbers, m and n, I can see that sum becomes m plus n.
Basically, it is not a and b, it is m and n. So, the sum of m and n becomes 10 from here. According to case 1, m plus n value is 10. Either do 9 plus 1 or 8 plus 2, sum is 10. Now let's talk about case number 2. In case number 2, if I take p value as 5, how much should I take p value? I should take 5. If I take gcd as 5, then for this bracket, 1 will be left.
This means that x plus 3y minus 2xy and 11 in plus is equal to 1. On both sides, multiply by 2 because we have to factorise. Kids know this. If we multiply by 2, it will be 2x minus 4xy, write it first. And write 236y plus in the last.
And from 11, 2 is 22. And if we throw it there, it will be minus 22. So, 2 minus 22 will be. Okay. You need minus 3 here to factorise. So, we put minus 3 here also. Okay.
What is the common value of 2x from both? 1 minus 2y. Very good. and take minus 3 common from both and again 1-2y that is equal to minus 20 and minus 3, minus 23 2x-3 is one factor and one factor is 1-2y that is equal to minus 23, minus this bracket so this 2x-3 and 2y-1 will be equal to 23 so there is only one possibility 23x1, there is no other possibility, there is a prime number in front so once it is 2x-3 is equal to 23 and 2y-1 is equal to 2y-1 ok here is one more possibility 5 for 3, we did not use that, we will do that too, wait 2y-1 is equal to, if I do 23, then the value of y will come out from here, 24 upon 2 means 12, will the value of y come 12?
and from here, if we add minus 3, it will be 26, so the value of x will be 13 x value is 13, y value is 12 ok ok and if I reverse it, what will happen? if I reverse it, then if I equal 2x minus 3 to 1 then the value of x will be 2 and if I equal 2y minus 1 to No, I have made both equal to 23. Wait, wait, wait, wait, wait. One minute, one minute. Here we will not make it equal to 23. Right? If we make 2x-3 equal to 23, then I will make x value of 2y-1 equal to 1. So, from here, y value will be 1. Clear?
And if we make 2x-3 equal to 1, then 2y-3 will be equal to 23. So, in that situation, in that situation, see, this is a case. and this is the next case ok so 2y-3 is equal to 23 so y is equal to 12 ok so in that situation also you understand that 13 plus 1 is 14 so when I am calculating m plus n when I am calculating m plus n understand from here when I am calculating m plus n then p will be common from px and py where is y? So here the value of x plus y is 13 plus 1 is 14 and here 12 plus 2 is also 14. So the value of m plus n will come from here 14 times the greatest common divisor is 5. So 14 times 5 is 70. The maximum possible value of m plus n is 70. The case from that case was 10. And here we have one case in which we discuss that case here. if I break this 15 in 5 and 3, then the case will remain here.
If I break it in 5 and 3, then 2y-1, if I equal that to 5, then the value of y will be 3. And if I equal 2x-3 to 3, then the value of x will be 6 upon 2 is 3. So in that situation, x plus y will be 3 plus 3 is 6. So the value of m plus n is 6 only. So this is not our maximum value. In the next case, if I would have given 5 to 2x minus 3, then the value of x would have been 4. And if I would have given 3 to 2y minus 1, then the value of y would have been 2. So in that situation, the sum of x and y would have been 6. So m plus n would have been 6. So that is not the maximum value.
so the maximum value of M plus N is 70 this was a great question of IOQM 2022 this was a great answer to the ultimate questions let's move ahead let's see its printed solution this is the printed solution Okay, and in its printed solution, the maximum value is 70. In two cases, it is 70. So, 70 is the answer. Whether it is 13 and 1 or 12 and 2, both cases have 70 maximum value. So, the maximum value of this question is 70. Hope you understood. Let's move ahead. Yes, after this, our next topic is primes.
What is the name of the topic? Primes. Do you know what prime numbers are?
We cannot discuss much in this lecture But we understand what are primes Prime numbers are those numbers where we can divide by our own or by one. These numbers have exactly two factors Two distinct divisors or factors One and the number itself Any integer p So for that, what are those two things? 1 and that P itself. If there are only two divisors, then what will we call such numbers?
We will call them prime numbers. Make a list of prime numbers. The smallest prime number is 2. What is the smallest prime number? 2. Okay, there are exactly two factors of 2. Which ones? In 2, 1 is also divided and in 2, 2 is also divided.
Apart from that, no one is divided in 2. Clear? Okay. Wait.
Ok, let's talk about this So in 2, either 1 is divided or 2 is divided by itself Similarly, in 3 either 1 is divided or 2 is divided by itself 5, 7, 11, 13, 17, 19, so on There are many prime numbers in the world And questions are made based on these prime numbers In IUQM, and those questions will be discussed on them too So, basically prime numbers are those which have two fixed factors, one and itself. There are some properties of prime numbers. What are the properties of prime numbers?
If a prime number P divides AB, who is it dividing? AB, the product of A and B. And we are not sure which of A and B it is dividing. So, this is simple.
Either that prime number is dividing A or B. either A or B it can be that A and B are also divided like 2 is dividing 4 and 2 is dividing 6 2 is dividing 4 and 2 is dividing 6 so in that situation 2 will divide 4 times 6 means 24 so when 2 is dividing 24 then we can't say so it can be that I am dividing this also and this also or I am dividing this also or this also or I am dividing one of them, any possibility can be there but one possibility will always be that either he will divide this or he will divide this or he will divide both of them it can't be that neither of them should be divided it can't be that neither of them should be divided ok, next point next second point, what does it say it provides a to the power n p divides what? a to the power n so this implies that p divides a too if p divides any number of any power if p is a prime number and divides any number of any power then basically p knows how to divide that number too like 2 divides 4 to the power 100 so this implies that 2 divides 4 too only the one sitting here should be prime what should happen? prime number should happen next thing If P is dividing A in that situation, then who will be divided by P to the power of N? A to the power of N.
N should belong to natural numbers. It is fixed. Next point is, every integer is greater than 1. Every integer greater than 1 is divisible by at least 1 prime. Think of any integer greater than 1 in your mind.
The one which divides it, there will be at least one prime number in the world. Do you understand? It is a necessity.
It will definitely happen. Okay? For example, if you think of any number bigger than 1, then you get 2 as integer. There is a prime number 2 that divides 2. There is 3 in the mind.
There is a prime number that divides 3. There is 3, right? There is 4. There is a prime number 2 that divides 4. Okay, sir? There should be no problem.
Let's move ahead. What is next? If n is greater than 1, then there is at least one prime p such that there is a prime number p in the world.
If n is greater than 1, then a prime number P will be such that it will lie between n and 2n. means between that number and its double, a prime number will always lie like if you think of any number, say 10 so double of 10 and 10 is 20 between 10 and 20, at least one prime number will definitely come one prime number will definitely come a slight generalization for n greater than 3 if n is greater than 3, then we have another generalization for that that there always exists at least one prime there will definitely exist a prime number p which will be greater than n, but 2n-2 will be smaller than n any number which is bigger than 3 like 5 is equal to n so 5 and 2n-2 5 to 10-2 will be 8 so there will be a prime number between 5 and 8 7 is coming The main thing is prime number. Did you understand?
The special thing about prime number is that there can be only two factors. One or itself. Remember this. If in any situation, I am asked to prove a number as prime, if I am asked to prove an expression as prime, then the first thing I will do is I will make factors of that expression. What will I make?
I will make factors. What will I do after making factors? I would like to have one factor. all other factors will be 1 because there can't be more than 2 factors of any prime number and even in those 2 factors, 1 factor should be 1 so I will try that whenever I do factorization then most of the factors other than 1 factor will be prime numbers clear? no no no, it should be 1, not prime it should be 1, clear?
let's move ahead, ok? Let's see a question. What is the question?
Show that for any integer n, the number n power 4 minus 20 n square plus 4 is not a prime number. We have to show that for any integer n, this expression n power 4 minus 20 n square plus 4 is not a prime number. For any integer n, this expression n power 4 minus 20 n square plus 4 is not a prime number.
prime number nahi hoga. Yeh prime number nahi hoga. Clear?
Achha, toh kya karein? Pahle is question ko dekhte iska factorization karo. Kya karo beta?
Factorization karo. Thik hai? Toh n par 4 minus 20 n square Thik hai saab?
Aur plus me kitna? 4. Clear hai beta? Isko factorize karna socha hamne.
Isko factorize karne ka hamne socha. Thik hai saab? Toh n par 4 is written as n square square minus 20n square we left that for once plus 4 is 2 square so a square and b square are seen so I want 2ab to come in minus so I will keep 2 in minus 2 into n square in place of a and 2 in place of b so 2 2 is 4 minus 4n square this is 4n square minus but how much did I have?
minus 20n square ok so how much is left? minus 16n square is left So write the 16n square of minus in front. Where to write the 16n square of minus?
Write it in front. Any problem till here? Do you understand the story till here?
You must be able to understand it. What will we do after this? I made a square plus b square minus 2ab.
Made the whole square of n square minus 2. What did we make of n square minus 2? Whole square. In minus, 16n square is basically 4n's whole square. So here a square minus b square came.
so what we will do is, a plus b into a minus b so this will be n square minus, no no, plus 4n minus 2 and we will write n square minus 4n minus 2 we have factorized this as soon as we factorized, after factorizing, it immediately came to mind that 2 factors are being made here, how many factors are being made? 2 factors ok sir, so what to do if 2 factors are being made so the 2 factors that are being made are from these 2 factors, because if this thing Prime should be maintained Prime is that which has only two factors One is one and the other is itself Right? One and itself So we have to try that One of these two One of these two should be maintained One should be maintained So first case What to do in one?
If it becomes minus one then also there is no problem If it becomes minus one then also there is no problem so we will try case 1 in case 1 we tried n square minus 4n sorry, plus 4n minus 2, what did we put here? we put here plus 1, we made case 2 case 2, that n square plus 4n minus 2, we keep it minus 1. We keep it 1 and then minus 1. And I want to check that is there any integer value of n to keep it equal to 1? If there is any integer value of n, then I will put that integer value here and check that is there any prime number to be made by putting that integer? Yes, because if one bracket is 1 and the result of the second bracket is prime number, then it is...
for any integer value n, result prime number can be there but for that, any one bracket has to be 1 any one bracket has to be 1, 1 or minus 1 so first put 1, first bracket is equal to 1 then first bracket is equal to minus 1 then case number 3 in case number 3, n square minus 4n minus 2 is equal to 1 and case number 4 okay sir n square minus 4n minus 2 this is equal to minus 1 clear? okay, let's think from here 1 goes there so it will be plus 1 no no, 1 goes there so it will be minus 1 so this will be n square minus 4n minus 3 equal to 0 okay, this is looking quadratic so is there any integer value of n or not for this what to do directly by applying quadratic formula, find n's value so if we apply quadratic formula then it will be minus b so minus minus plus 4 plus minus under root b square so, minus 4 square plus 16 minus 4 into a into c, so 4 into 1 into 3 so, 4 into 3 is 12, minus 12 minus 9 is plus 12 16 and 12, so 28 how much will be in the upon? 2 so, if you simplify and divide 2, then it will be 2 plus minus we write 28, 2 root 7, 2 is cut, root 7 is left so from here integer is not there n value is 2 plus minus root 7 which is irrational and not integer n is not equal to integer no integer is there hope is on the world, let's see next one minus 1 will be plus 1, so n square plus 4n one more mistake, here was plus then why we did minus, here will be plus so minus will come here so minus will come here too but the thing is that n is not an integer n square plus 4n minus 1 will come so minus 2 plus 1 will be minus 1 that is equal to 0 so the value of n will come minus 4 plus minus minus 4 minus 4 plus minus under root 4 square 16 4 square 16 minus 4ac so 4 will be 16 plus 4 will be 20 upon will be 2 so 2 will be minus 2 plus minus root 5 whatever n value is here is not integer because it is irrational so here also n value is not integer now let's check in this, if we throw 1 there then n square minus 4n and minus 3 will be there so we will have 0 so here n will be 4 plus minus under root 28 upon 2 which is equal to 2 plus minus root 7 and here also n will be n square minus 4n plus 1 minus 2 plus 1 minus 1 that is equal to 0 so here n will be 4 plus minus under root b square 16 you if it is minus 4ac then it will be plus 20 upon 2 so that will be equal to 2 plus minus root 5 here also n is not equal to integer so here also there is no integer in all cases there is no integer so you got to know neither this bracket nor this bracket, any one of them is ready to be 1 and if there is no 1 in both the brackets then both of them can take any value other than 1 we don't know if they will take 0 or not if you check its discriminant if 1 is 0 then the number is 0 if 0 is not a prime number then leave the 0 case if there is no 1 in both the brackets then this will not be a prime number so this implies that For any integer n, for any integer n, for any integer n, for any integer n, the number, the number, the number n power 4 minus 20n square plus 4 is not a prime number.
This prime number will never happen. Brother, this is absolutely proof, right? It is obvious that this prime number will not be for any integer value of n Because one of these two brackets should have been 1 It was bad that not even one of them was 1 That means, for one of them, n's value integer did not come So there is no integer value for which 1 or minus 1 can be So this prime number cannot be for any integer value of n I hope you understood this story very well So for today, we will end the story here ok sir, so for today we will end the story here hope you understood the story till here ok, so see you in next class we will talk about next chapter we talked about primes but we couldn't talk about composite in next class we will talk about some good primes then we will talk about composite number and we will move ahead in this chapter about number theory you must have understood the chapter till here solve the questions well we are bringing all the topic wise and prepare and comment that's all for today, thank you, thanks to all of you bye bye, see you in the next class thank you