Chinese Remainder Theorem -- Number Theory 11

  Рет қаралды 39,773

Michael Penn

Michael Penn

2 жыл бұрын

Suggest a problem: forms.gle/ea7Pw7HcKePGB4my5
Please Subscribe: kzbin.info...
Patreon: / michaelpennmath
Merch: teespring.com/stores/michael-...
Personal Website: www.michael-penn.net
Randolph College Math: www.randolphcollege.edu/mathem...
Randolph College Math and Science on Facebook: / randolph.science
Research Gate profile: www.researchgate.net/profile/...
Google Scholar profile: scholar.google.com/citations?...
If you are going to use an ad-blocker, considering using brave and tipping me BAT!
brave.com/sdp793
Buy textbooks here and help me out: amzn.to/31Bj9ye
Buy an amazon gift card and help me out: amzn.to/2PComAf
Books I like:
Sacred Mathematics: Japanese Temple Geometry: amzn.to/2ZIadH9
Electricity and Magnetism for Mathematicians: amzn.to/2H8ePzL
Abstract Algebra:
Judson(online): abstract.ups.edu/
Judson(print): amzn.to/2Xg92wD
Dummit and Foote: amzn.to/2zYOrok
Gallian: amzn.to/2zg4YEo
Artin: amzn.to/2LQ8l7C
Differential Forms:
Bachman: amzn.to/2z9wljH
Number Theory:
Crisman(online): math.gordon.edu/ntic/
Strayer: amzn.to/3bXwLah
Andrews: amzn.to/2zWlOZ0
Analysis:
Abbot: amzn.to/3cwYtuF
How to think about Analysis: amzn.to/2AIhwVm
Calculus:
OpenStax(online): openstax.org/subjects/math
OpenStax Vol 1: amzn.to/2zlreN8
OpenStax Vol 2: amzn.to/2TtwoxH
OpenStax Vol 3: amzn.to/3bPJ3Bn
My Filming Equipment:
Camera: amzn.to/3kx2JzE
Lense: amzn.to/2PFxPXA
Audio Recorder: amzn.to/2XLzkaZ
Microphones: amzn.to/3fJED0T
Lights: amzn.to/2XHxRT0
White Chalk: amzn.to/3ipu3Oh
Color Chalk: amzn.to/2XL6eIJ

Пікірлер: 58
@williamperez-hernandez3968
@williamperez-hernandez3968 2 жыл бұрын
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).
@emperornortoni2871
@emperornortoni2871 2 жыл бұрын
I earnestly thought I was losing my mind. Thanks.
@matematicacommarcospaulo
@matematicacommarcospaulo 2 жыл бұрын
How can I prove that if each n_i divides x-y, then the product of all n_i also divides x-y?
@williamperez-hernandez3968
@williamperez-hernandez3968 2 жыл бұрын
@@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.
@pandawagurning
@pandawagurning 2 жыл бұрын
@@matematicacommarcospaulo GCD(n_1,n_2,n_3,....,n_i)=1
@telnobynoyator_6183
@telnobynoyator_6183 2 жыл бұрын
Got me a bit confused haha
@miasbeck
@miasbeck 2 жыл бұрын
Always good to have the Mandalorian at your side to tackle a system of congruences.
@randobravo4335
@randobravo4335 2 жыл бұрын
This guy is so entertaining as a math teacher ..I hear he even does back flips !? 🤔☺️
@user-cr4fc3nj3i
@user-cr4fc3nj3i 2 жыл бұрын
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 😂
@lucacastenetto1230
@lucacastenetto1230 2 жыл бұрын
Hahahahahhahah thank you for sharing
@anonymouskumar8576
@anonymouskumar8576 Ай бұрын
😂
@goodplacetostop2973
@goodplacetostop2973 2 жыл бұрын
26:34 Homework 26:57 Good Place To Stop
@lorencbushi5923
@lorencbushi5923 2 жыл бұрын
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.
@theRealdesaro
@theRealdesaro Жыл бұрын
what's the name of that theorem?
@Chris_5318
@Chris_5318 2 жыл бұрын
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).
@randomdude9135
@randomdude9135 2 жыл бұрын
Wow
@maxblack493
@maxblack493 2 жыл бұрын
Excellent. Thank you.
@fierydino9402
@fierydino9402 Жыл бұрын
Thank you!
@user-cr4fc3nj3i
@user-cr4fc3nj3i 2 жыл бұрын
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.
@Boringpenguin
@Boringpenguin 2 жыл бұрын
(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.
@bobh6728
@bobh6728 2 жыл бұрын
Help me understand. What does the inverse mean in 3(inverse) (mod 4)? Is it 1/3? I’m missing something.
@DilipKumar-ns2kl
@DilipKumar-ns2kl 2 жыл бұрын
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).
@sentipy8990
@sentipy8990 2 жыл бұрын
@@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)
@bobh6728
@bobh6728 2 жыл бұрын
@@sentipy8990 thanks. That was the first time I heard of that and missed the fairly obvious definition.
@pdjibril
@pdjibril Жыл бұрын
Excellent!
@user-fz9go8pj4t
@user-fz9go8pj4t 2 жыл бұрын
Dear Michael, I want to request something from you. Could you, please, give a series of lectures on KZbin 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....
@agrajyadav2951
@agrajyadav2951 2 жыл бұрын
im surprised its called chinese remainder theorem and europeans didnt "rediscover" it and publish it as eg George's theorem. Thanks Gauss!
@skwbusaidi
@skwbusaidi 2 жыл бұрын
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)
@jiahao2709
@jiahao2709 Жыл бұрын
by the way, are there any course note for your wonderful lecture?
@GKinWor
@GKinWor 2 жыл бұрын
hha perfect because i did NOT attend my lecture and it was on this
@ConManAU
@ConManAU 2 жыл бұрын
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?”
@schrodingerbracat2927
@schrodingerbracat2927 2 жыл бұрын
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) >
@randomdude9135
@randomdude9135 2 жыл бұрын
@@schrodingerbracat2927 what's the python program for that??
@schrodingerbracat2927
@schrodingerbracat2927 2 жыл бұрын
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) >
@endormaster2315
@endormaster2315 Жыл бұрын
Thank you, I have corrected my solutions via yours.
@thelilpippin
@thelilpippin Жыл бұрын
Hi Michael, I want to get a chalkboard like this, where did you get it?
@r.maelstrom4810
@r.maelstrom4810 2 жыл бұрын
It's the other way round: it's x == 1(mod 4) which are special cases of x == 1(mod2)
@exvaran
@exvaran 2 жыл бұрын
12:33 Nice
@briana5708
@briana5708 2 жыл бұрын
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.
@absolutezero9874
@absolutezero9874 Ай бұрын
Hi Why is X1 congruent to inverse of N (mod n1)?
@jimallysonnevado3973
@jimallysonnevado3973 2 жыл бұрын
Second problem no need to go through the steps. 6 satisfies all.
@efrensumortin1474
@efrensumortin1474 2 жыл бұрын
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??
@tejasgambhir6457
@tejasgambhir6457 2 күн бұрын
warm up : 1) x = 37 2) X = 126
@yeech
@yeech 2 жыл бұрын
Sorry I would like to ask: Why 2^-1(mod7) is congruent to 4(mod7)?
@pakornlim4343
@pakornlim4343 2 жыл бұрын
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.
@Boringpenguin
@Boringpenguin 2 жыл бұрын
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
@yeech
@yeech 2 жыл бұрын
Thank you very much!!! I understand now!!
@absolutezero9874
@absolutezero9874 Ай бұрын
@@Boringpenguin Hi New to this CRT Why is X1 congruent to inverse of N (mod n1), for eg Thank you?
@iabervon
@iabervon 2 жыл бұрын
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.
@WillBillDillPickle
@WillBillDillPickle Жыл бұрын
chad!
@justindilabio7155
@justindilabio7155 Жыл бұрын
what heppen to your arm/pinky?
@ivayloivanov5766
@ivayloivanov5766 Жыл бұрын
Can you help me with this, please: x ≡ 2 (mod 11) x ≡ 9 (mod 15) x ≡ 7 (mod 9) x ≡ 5 (mod 7) ?
@holyshit922
@holyshit922 Жыл бұрын
What happened with his left hand Was everything ok ?
@holyshit922
@holyshit922 Жыл бұрын
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
@randobravo4335
@randobravo4335 2 жыл бұрын
This is a good lecture but this topic of as to be in person ..this is a Gauss lecture from Gottingen and is complex
@klementhajrullaj1222
@klementhajrullaj1222 2 жыл бұрын
What has happened with your hand?! 😲😲😲
@MisterPenguin42
@MisterPenguin42 2 жыл бұрын
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.
@paulkohl9267
@paulkohl9267 2 жыл бұрын
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 ....
Euler's Theorem -- Number Theory 12
23:53
Michael Penn
Рет қаралды 22 М.
Chinese Remainder Theorem and Cards - Numberphile
11:13
Numberphile
Рет қаралды 327 М.
A pack of chips with a surprise 🤣😍❤️ #demariki
00:14
Demariki
Рет қаралды 39 МЛН
Final muy inesperado 🥹
00:48
Juan De Dios Pantoja
Рет қаралды 15 МЛН
Which one is the best? #katebrush #shorts
00:12
Kate Brush
Рет қаралды 22 МЛН
Wilson's Theorem -- Number Theory 14
29:02
Michael Penn
Рет қаралды 29 М.
Chinese Remainder Theorem | Sun Tzu's Theorem
11:36
Calculus by Christee
Рет қаралды 31 М.
Introduction to number theory lecture 13. The Chinese remainder theorem.
34:47
FUN Ecuadorian Math Olympiad Number Theory Problem
19:50
Michael Penn
Рет қаралды 40 М.
Chinese Remainder Theorem
15:11
Prime Newtons
Рет қаралды 3,1 М.
The Reciprocals of Primes - Numberphile
15:31
Numberphile
Рет қаралды 1,6 МЛН
Solving linear congruences -- Number Theory 10
18:06
Michael Penn
Рет қаралды 31 М.
What are these symbols? - Numberphile
21:19
Numberphile
Рет қаралды 221 М.
Chinese Remainder Theorem
13:15
Maths with Jay
Рет қаралды 433 М.
A pack of chips with a surprise 🤣😍❤️ #demariki
00:14
Demariki
Рет қаралды 39 МЛН