8:55 The divisions are backwards, should be n_i divides (x-y), for all n_i. Therefore x-y must have the product of all n_i, so it is a multiple of N, giving the result x == y (mod N).
@@matematicacommarcospaulo Since n_i and n_j are relative primes, the prime factorization of n_i has primes not present in n_j. Therefore, x-y has all the primes of n_i and n_j in its prime factorization. This is true for the complete set {n_k}. So N has product of all different primes forming the set, as also does x-y.
The inverse calculations can be done more systematically by noting that b^(-1) = b^(φ(n) - 1) (mod n) e.g. 2^(-1) = 2^(4-1) = 2^3 = 8 = 3 (mod 5) Note that for the CRT we have guaranteed that gcd(b,n) = 1 and so it satisfies the conditions of Euler's theorem (FLT generalisation).
output from my Python program:- To solve system of congruences:- x = 4 (mod 11) x = 3 (mod 17) Solving by sum construction ... (187 / 11)^-1 = 17^-1 = 2 mod 11 (187 / 17)^-1 = 11^-1 = -3 mod 17 sum = 4*2*17 + 3*-3*11 = 37 Conclusion: x = 37 (mod 187) To solve system of congruences:- x = 0 (mod 2) x = 0 (mod 3) x = 1 (mod 5) x = 6 (mod 7) Solving by sum construction ... (210 / 2)^-1 = 105^-1 = 1 mod 2 (210 / 3)^-1 = 70^-1 = 1 mod 3 (210 / 5)^-1 = 42^-1 = -2 mod 5 (210 / 7)^-1 = 30^-1 = -3 mod 7 sum = 0*1*105 + 0*1*70 + 1*-2*42 + 6*-3*30 = -624 Conclusion: x = 6 (mod 210) >
Theres a really nice generalization of the CRT for ideals of a commutative ring which lets you apply it in a wider context. It can also be used to get a simple proof of the multiplicativity of the totient function.
Just a trivial thing I've noticed at the "table" at 24:38. From the congruences "3⁻¹ (mod 4) ≡ 3 (mod 4)" and "2⁻¹ (mod 3) ≡ 2 (mod 3)", I got inspired and then realized that it is always true that "(n-1)⁻¹ (mod n) ≡ (n-1) (mod n)" The proof is trivial and is left as an exercise to the reader.
Check this.Your first example can be generalized (in fact any example to solve given the divisors) If x=a(mod 3), x=b(mod7) & x=c(mod10) then required number N is given by N=70a+120b+21c (mod 210).
@@bobh6728 Inverse module of number "a" mod n is such number "x " so that a * x ≡ 1 (mod n). For instance inverse module of 3 mod 5 is 2 because 3 * 2 ≡ 1 (mod 5)
Example2 x =1 ( mod 4) ---eq1 x=3 (mod 10) --eq2 x= 8 (mod 15) -- eq 3 From eq 1 x= 4a +1 ---eq4 Sub eq4 in eq 2 4a+1 = 3 ( mod 10) 4a = 2 ( mod 10) We want to divide by 2 but remember that gcd (2, 10) = 2 so we need to devide the mod 10 also by 2 2a = 1 ( mod 5) a = 3 ( mod 5) a = 5b +3 ---eq5 Sub eq5 in 4 x = 4( 5b+3) + 1 x= 20b + 13 ---eq6 Sub eq6 in eq3 20b+13 = 8 ( mod 15) 20b = -5 ( mod 15) 5b = 10 ( mod 15) We need to devide by 5 but gcd ( 5, 15) is 5 so the mod 15 is also devide by gcd ( 5,15) b= 2 ( mod 3) b= 3c+2 --eq7 Sub eq7 in eq6 x= 20(3c+2) +13 x= 60c + 53 x= 53 ( mod 60)
I think people need to remember the use of 'eyeballing a solution', for the warmup part 2 it looks longer but x == 0 (mod 2) => it's even x == 0 (mod 3) => it's divisible by 3, what's the first number that's both? 6. 6 (mod 5) == 1, what we wanted. 6 (mod 7) == 6 again what we wanted. Sometimes it's good to get a good idea of what might be the right solution, before diving straight in.
At 16:37, before he said "and that will be our "nicest" answer", I was already doing the calculation in my head. I wasn't being careful because it is just simple arithmetic, just 689-630. Then I started to take my time and I got "69" exactly at the same timing that when he said "the "nicest" answer". And I was like "oh hahahaha I see what you did there". Then when he wrote down 59 I then quickly realized how dumb I was 😂
Dear Michael, I want to request something from you. Could you, please, give a series of lectures on TH-cam on some more advanced topics, like you did with your research interest, the vertex algebra. I mean here particularly some analytic number theory, like maybe the Prime Number Theorem (to deal with the famous asymptotic of the number of primes up to something), or maybe some algebraic number theory, geometry of numbers, etc. That's on number theory. But not only that, if you could include some measure theory, like some ergodic properties, etc. I mean if you could do something on the undergraduate upper level or the first year of graduate level courses. I know that is much of a hassle, but please consider doing that once a while when you have some time... please....
Doing the second homework problem, I figured that I could apply the CRT to pairs of the equations and combine them, so I started by solving the mod 2 and 5 giving x = 6 mod 10 and the mod 3 and 7 giving x = 6 mod 21, then I stared at it for a second and went “… is it just 6?”
Output from my Python program, but yea, I could have guessed the answer. To solve system of congruences:- x = 0 (mod 2) x = 0 (mod 3) x = 1 (mod 5) x = 6 (mod 7) Solving by the pairwise method ... Solving CRT pair x = 0 (mod 2) x = 0 (mod 3) Pair soln: x = 0 (mod 6) Solving CRT pair x = 0 (mod 6) x = 1 (mod 5) Pair soln: x = 6 (mod 30) Solving CRT pair x = 6 (mod 30) x = 6 (mod 7) Pair soln: x = 6 (mod 210) Solving by sum construction ... (210 / 2)^-1 = 105^-1 = 1 mod 2 (210 / 3)^-1 = 70^-1 = 1 mod 3 (210 / 5)^-1 = 42^-1 = -2 mod 5 (210 / 7)^-1 = 30^-1 = -3 mod 7 sum = 0*1*105 + 0*1*70 + 1*-2*42 + 6*-3*30 = -624 Conclusion: x = 6 (mod 210) >
I had been taught differently x = 2 mod 3 x = 3 mod 7 x = 9 mod 10 x = 2 mod 3 x = 3 mod 7 1 = (-2)*3+1*7 x = ((-2)*3*3 + (1)*7*2 ) mod 21 x = 17 mod 21 x = 17 mod 21 x = 9 mod 10 1 = 1*21 + (-2)*10 x = (1*21*9 + (-2)*10*17) mod 210 x = (189 - 340) mod 210 x = (189 - 340+210)mod 210 x = 59 mod 210
At 25:30 Michael says we need to check this solution 53 against the original problem. Is that really necessary? Or is that just a double check for errors? I can't see any case where the solution wouldn't work if you do the previous steps correctly.
Since 4 and 15 are relatively prime and their product is a multiple of 10, you could solve the system with just 4 and 15, and check whether the answer works for 10. Also, if there are two congruences that are easy to combine, you can do that and have fewer, larger congruences to work with. For example, if you've got several that are 0 (mod something), you can find x to be 0 mod their lcm without working out any of the details, since you're going to multiply by a_i=0. It's also worth noting that you can reuse a lot of computation if you want to do a bunch of systems if you can pick the n_i to be the same for all the systems.
Nice video covering CRT (not Critical Race Theory but Chinese Remainder Theorem). Does anyone think it is crazy that the chinese remainder theorem reminds me of partial derivatives and maybe the chain rule? x ≡ r (mod m) analog ∂ x / ∂ m = r ....
8:55 The divisions are backwards, should be n_i divides (x-y), for all n_i. Therefore x-y must have the product of all n_i, so it is a multiple of N, giving the result x == y (mod N).
I earnestly thought I was losing my mind. Thanks.
How can I prove that if each n_i divides x-y, then the product of all n_i also divides x-y?
@@matematicacommarcospaulo Since n_i and n_j are relative primes, the prime factorization of n_i has primes not present in n_j. Therefore, x-y has all the primes of n_i and n_j in its prime factorization. This is true for the complete set {n_k}. So N has product of all different primes forming the set, as also does x-y.
@@matematicacommarcospaulo
GCD(n_1,n_2,n_3,....,n_i)=1
Got me a bit confused haha
Always good to have the Mandalorian at your side to tackle a system of congruences.
This guy is so entertaining as a math teacher ..I hear he even does back flips !? 🤔☺️
The inverse calculations can be done more systematically by noting that
b^(-1) = b^(φ(n) - 1) (mod n)
e.g. 2^(-1) = 2^(4-1) = 2^3 = 8 = 3 (mod 5)
Note that for the CRT we have guaranteed that gcd(b,n) = 1 and so it satisfies the conditions of Euler's theorem (FLT generalisation).
Wow
output from my Python program:-
To solve system of congruences:-
x = 4 (mod 11)
x = 3 (mod 17)
Solving by sum construction ...
(187 / 11)^-1 = 17^-1 = 2 mod 11
(187 / 17)^-1 = 11^-1 = -3 mod 17
sum = 4*2*17 + 3*-3*11 = 37
Conclusion: x = 37 (mod 187)
To solve system of congruences:-
x = 0 (mod 2)
x = 0 (mod 3)
x = 1 (mod 5)
x = 6 (mod 7)
Solving by sum construction ...
(210 / 2)^-1 = 105^-1 = 1 mod 2
(210 / 3)^-1 = 70^-1 = 1 mod 3
(210 / 5)^-1 = 42^-1 = -2 mod 5
(210 / 7)^-1 = 30^-1 = -3 mod 7
sum = 0*1*105 + 0*1*70 + 1*-2*42 + 6*-3*30 = -624
Conclusion: x = 6 (mod 210)
>
Thank you, I have corrected my solutions via yours.
Theres a really nice generalization of the CRT for ideals of a commutative ring which lets you apply it in a wider context. It can also be used to get a simple proof of the multiplicativity of the totient function.
what's the name of that theorem?
26:34 Homework
26:57 Good Place To Stop
Just a trivial thing I've noticed at the "table" at 24:38. From the congruences "3⁻¹ (mod 4) ≡ 3 (mod 4)" and "2⁻¹ (mod 3) ≡ 2 (mod 3)", I got inspired and then realized that it is always true that "(n-1)⁻¹ (mod n) ≡ (n-1) (mod n)"
The proof is trivial and is left as an exercise to the reader.
(n-1)(n-1) = n^2 - 2n +1 ≡ 1 (mod n), or even simpler,
(n-1)(n-1) ≡ (-1)(-1) ≡ 1 (mod n),
so n-1 is always its own inverse modulo n.
Help me understand. What does the inverse mean in 3(inverse) (mod 4)?
Is it 1/3? I’m missing something.
Check this.Your first example can be generalized (in fact any example to solve
given the divisors)
If x=a(mod 3), x=b(mod7) & x=c(mod10)
then required number N is given by
N=70a+120b+21c (mod 210).
@@bobh6728 Inverse module of number "a" mod n is such number "x " so that a * x ≡ 1 (mod n). For instance inverse module of 3 mod 5 is 2 because 3 * 2 ≡ 1 (mod 5)
@@sentipy8990 thanks. That was the first time I heard of that and missed the fairly obvious definition.
Example2
x =1 ( mod 4) ---eq1
x=3 (mod 10) --eq2
x= 8 (mod 15) -- eq 3
From eq 1
x= 4a +1 ---eq4
Sub eq4 in eq 2
4a+1 = 3 ( mod 10)
4a = 2 ( mod 10)
We want to divide by 2 but remember that gcd (2, 10) = 2 so we need to devide the mod 10 also by 2
2a = 1 ( mod 5)
a = 3 ( mod 5)
a = 5b +3 ---eq5
Sub eq5 in 4
x = 4( 5b+3) + 1
x= 20b + 13 ---eq6
Sub eq6 in eq3
20b+13 = 8 ( mod 15)
20b = -5 ( mod 15)
5b = 10 ( mod 15)
We need to devide by 5 but gcd ( 5, 15) is 5 so the mod 15 is also devide by gcd ( 5,15)
b= 2 ( mod 3)
b= 3c+2 --eq7
Sub eq7 in eq6
x= 20(3c+2) +13
x= 60c + 53
x= 53 ( mod 60)
I think people need to remember the use of 'eyeballing a solution', for the warmup part 2 it looks longer but
x == 0 (mod 2) => it's even
x == 0 (mod 3) => it's divisible by 3, what's the first number that's both? 6.
6 (mod 5) == 1, what we wanted.
6 (mod 7) == 6 again what we wanted.
Sometimes it's good to get a good idea of what might be the right solution, before diving straight in.
At 16:37, before he said "and that will be our "nicest" answer", I was already doing the calculation in my head. I wasn't being careful because it is just simple arithmetic, just 689-630. Then I started to take my time and I got "69" exactly at the same timing that when he said "the "nicest" answer". And I was like "oh hahahaha I see what you did there".
Then when he wrote down 59 I then quickly realized how dumb I was 😂
Hahahahahhahah thank you for sharing
😂
Dear Michael, I want to request something from you. Could you, please, give a series of lectures on TH-cam on some more advanced topics, like you did with your research interest, the vertex algebra. I mean here particularly some analytic number theory, like maybe the Prime Number Theorem (to deal with the famous asymptotic of the number of primes up to something), or maybe some algebraic number theory, geometry of numbers, etc. That's on number theory. But not only that, if you could include some measure theory, like some ergodic properties, etc. I mean if you could do something on the undergraduate upper level or the first year of graduate level courses. I know that is much of a hassle, but please consider doing that once a while when you have some time... please....
im surprised its called chinese remainder theorem and europeans didnt "rediscover" it and publish it as eg George's theorem. Thanks Gauss!
Doing the second homework problem, I figured that I could apply the CRT to pairs of the equations and combine them, so I started by solving the mod 2 and 5 giving x = 6 mod 10 and the mod 3 and 7 giving x = 6 mod 21, then I stared at it for a second and went “… is it just 6?”
Output from my Python program, but yea, I could have guessed the answer.
To solve system of congruences:-
x = 0 (mod 2)
x = 0 (mod 3)
x = 1 (mod 5)
x = 6 (mod 7)
Solving by the pairwise method ...
Solving CRT pair
x = 0 (mod 2)
x = 0 (mod 3)
Pair soln: x = 0 (mod 6)
Solving CRT pair
x = 0 (mod 6)
x = 1 (mod 5)
Pair soln: x = 6 (mod 30)
Solving CRT pair
x = 6 (mod 30)
x = 6 (mod 7)
Pair soln: x = 6 (mod 210)
Solving by sum construction ...
(210 / 2)^-1 = 105^-1 = 1 mod 2
(210 / 3)^-1 = 70^-1 = 1 mod 3
(210 / 5)^-1 = 42^-1 = -2 mod 5
(210 / 7)^-1 = 30^-1 = -3 mod 7
sum = 0*1*105 + 0*1*70 + 1*-2*42 + 6*-3*30 = -624
Conclusion: x = 6 (mod 210)
>
@@schrodingerbracat2927 what's the python program for that??
I had been taught differently
x = 2 mod 3
x = 3 mod 7
x = 9 mod 10
x = 2 mod 3
x = 3 mod 7
1 = (-2)*3+1*7
x = ((-2)*3*3 + (1)*7*2 ) mod 21
x = 17 mod 21
x = 17 mod 21
x = 9 mod 10
1 = 1*21 + (-2)*10
x = (1*21*9 + (-2)*10*17) mod 210
x = (189 - 340) mod 210
x = (189 - 340+210)mod 210
x = 59 mod 210
12:33 Nice
What if one of the system is
X = y mod8 ?? How can we solve that?
Like X = 2mod12
X= 8mod30
X = Cmod20
How can i get C??
At 25:30 Michael says we need to check this solution 53 against the original problem. Is that really necessary? Or is that just a double check for errors? I can't see any case where the solution wouldn't work if you do the previous steps correctly.
It's the other way round: it's x == 1(mod 4) which are special cases of x == 1(mod2)
Hi Michael, I want to get a chalkboard like this, where did you get it?
hha perfect because i did NOT attend my lecture and it was on this
warm up :
1) x = 37
2) X = 126
What happened with his left hand
Was everything ok ?
Hi
Why is X1 congruent to inverse of N (mod n1)?
by the way, are there any course note for your wonderful lecture?
Thank you!
Second problem no need to go through the steps. 6 satisfies all.
Excellent!
what heppen to your arm/pinky?
Excellent. Thank you.
Sorry I would like to ask:
Why 2^-1(mod7) is congruent to 4(mod7)?
2inverse mod 7 means that
2 times 2inverse = 1 mod 7
but we found that
2 times 2inverse = 8 mod 7
so, 2inverse = 4 mod 7.
That is because (2)(4) = 8 ≡ 1 (mod 7)
We say a is the inverse of x modulo n if ax ≡ 1 (mod n), and we will usually denote a as x^-1
Thank you very much!!! I understand now!!
@@Boringpenguin
Hi
New to this CRT
Why is X1 congruent to inverse of N (mod n1), for eg
Thank you?
Can you help me with this, please:
x ≡ 2 (mod 11)
x ≡ 9 (mod 15)
x ≡ 7 (mod 9)
x ≡ 5 (mod 7) ?
This is a good lecture but this topic of as to be in person ..this is a Gauss lecture from Gottingen and is complex
Since 4 and 15 are relatively prime and their product is a multiple of 10, you could solve the system with just 4 and 15, and check whether the answer works for 10.
Also, if there are two congruences that are easy to combine, you can do that and have fewer, larger congruences to work with. For example, if you've got several that are 0 (mod something), you can find x to be 0 mod their lcm without working out any of the details, since you're going to multiply by a_i=0.
It's also worth noting that you can reuse a lot of computation if you want to do a bunch of systems if you can pick the n_i to be the same for all the systems.
chad!
What has happened with your hand?! 😲😲😲
Nice video covering CRT (not Critical Race Theory but Chinese Remainder Theorem). Does anyone think it is crazy that the chinese remainder theorem reminds me of partial derivatives and maybe the chain rule?
x ≡ r (mod m) analog ∂ x / ∂ m = r ....
I'm too stupid for this, but I really enjoy the videos, so I'm catching up on the math to understand what's going on.