CSIR NET MATHEMATICS | Number Theory | System of Congruence Equations Dec 2018 (Marks 3)

Hello friends, in this video we are going to discuss the problem of number theory from CSI on 8 December 2018. Example number 37 from booklet C marks three. Given integer a and b, let n(a, b) denote the number of positive integer k less than 100 such that k congruent to a modulo 9 and k congruent to b modulo 11, then which of the following statements First statement: n(a, b) equal to 1 for all integers a and b, third option: there exist integers a and b satisfying n(a, b) greater than 1, third option: there exist integers a and b satisfying n(a, b) equal to 0, fourth option: there exist integers a and b satisfying n(a, b) equal to 0 and there exist integer a and b satisfying n(a, b) greater than 1. This example contains the simultaneous congruence equations So first we recall some result associated with the simultaneous congruence equation. So first result: existence of solutions of system of congruence equation. x congruent to a modulo m1 and x congruent to b modulo m2 has solution if GCD of m1 and m2 divides a minus b. That means this simultaneous equation has solution if GCD of m1 and m2 should divide a minus b. Second result which is very well known result the Chinese Remainder Theorem and the statement is let m1 and m2 be co-prime integers and a and b integers then the simultaneous congruence equations x congruent to a modulo m1 and x congruent to b modulo m2 has unique solution for modulo m1 m2. That means for the modulo m1 m2, this simultaneous equation has unique solution if m1 and m2 are co-prime. The co-prime integer means that gcd should be 1. Now look at our example. We have given congruence equation k congruent to a modulo 9 and k congruent to b modulo 11. x is equal to k, m1 equal to 9, m2 equal to 11. Existence solution says that GCD of m1 m2 should divide a minus b. So GCD of m1 m2, GCD of 9 11 is 1 and 1 divides every integers therefore 1 divides a minus b. So therefore the result says that this system of congruence equation has solution. The second result Chinese remainder theorem. Now for the Chinese remainder theorem m1 m2 should be the co-prime so 9 and 11 as the gcd is 1 therefore they are co-prime and so it has unique solution for the modular m1 m2 equal to 99 and we consider only the positive integer k less than 100 therefore if k lies between 1 to 99 Then the system has unique solution. Which is the first option where nab equal to 1 for all integers a and b. That means n a b has only value 1 between 1 to 99 and hence the first option is correct. Thanks for watching. For more videos like, share, subscribe, press the bell icon of NextGenMaths.