System of congruences, modular arithmetic

Learn more math and science with brilliant.org, brilliant.org/blackpenredpen/ ,
first 200 people to sign up will get 20% off your subscription, and you can also support my channel! Thank you!
Read more about CRT: brilliant.org/wiki/chinese-re...
Solution to the question: brilliant.org/problems/thursd...
💪 Join our channel membership (for as low as $0.99 per month) to unlock several perks, including special badges and emojis during the livestreams: / @blackpenredpen
🏬 Shop math t-shirt & hoodies: teespring.com/stores/blackpen...
10% off with the code "TEESPRINGWELCOME10"
Equipment:
👉 Expo Markers (black, red, blue): amzn.to/2T3ijqW
👉 The whiteboard: amzn.to/2R38KX7
👉 Ultimate Integrals On Your Wall: teespring.com/calc-2-integral...
---------------------------------------------------------------------------------------------------

[@thiagoschnaider5828]

Honestly, I've been having to teach myself modular arithmetic and discrete mathematics for school and have been struggling for so long and this was SO freaking useful. You explain things so well, it's amazing. Thank you so much, man! Thank you for making math so easy to comprehend and so enjoyable.

[@tdiaz5555]

Small explanation on 15l congruent to 1l: 15l = 14l + 1l = 7*2l + 1l If you take (mod 7) of 14l and 1l 14l becomes 0 and 1l stays 1l

[@elijahbelov209]

Thanks

[@chhabisarkar9057]

Thanks , i was struggling in that

[@felixfong2667]

what are the |'s?

[@tdiaz5555]

@@felixfong2667 l was the letter he used in the video, it's a variable like x

[@kristeenchand3421]

Thanks alot :)

[@JalebJay]

Nice preview of the chinese remainder theorem.

[@rb1471]

For those that don't skip steps: 15L = 2 (mod 7) => 15L = 7k + 2 for some k in the integers Let k = 2T where T is an integer => 15L = 14T + 2 => L = 14T - 14L + 2 => L = 7(2T - 2L) + 2 Let H = (2T - 2L), then H is an integer. => L = 7H + 2 => L = 2 (mod 7)

[@nullplan01]

You can already reduce the first step. 15l =2 (mod 7) equivalent to l = 2 (mod 7) (since 15 = 2 * 7 + 1). Mod equations are linear. This means you can reduce factors and addends with the module. Not exponents, though. Also, while you can't divide (in general), you can multiply, and you can find a multiplicative inverse if the number you start with is relatively prime to the module. So if the second equation had simplified to 3k = 4 (mod 5), for such small modules, you can just try it out, and see that 2*3 = 6 = 1 (mod 5) (for larger modules you may need the extended Euclidean algorithm). So you can multiply both sides with 2 instead of dividing by 3 (which leads to k = 3).

[@rb1471]

Yes we know the rules, this was to provide a proof without skipping steps on how this is true: "15l =2 (mod 7) equivalent to l = 2 (mod 7) (since 15 = 2 * 7 + 1)."

[@rb1471]

zach p Yes I skipped many steps and didn't label any of them with Axioms. The purpose was a proof of the statement without skipping steps around the mod magic going on rather than a step by step guide through the axioms. I've taken a course which specifically required each step to be outlined and labeled like you mentioned and you quickly get used to it: 15L = 2 (mod 7) "Assumption" => 15L = 7k + 2 for any k in the integers, "by definition of mod" Choose k = 2T where T is an integer (2 and T are integers => 2T is an integer "closure") => 15L = 7(2T) + 2 "Substitution" => 15L = (7*2)T + 2 "Associative multiplication" => 15L = 14T + 2 "Multiplication" => 15L - 14L = (14T + 2) - 14L "Subtraction on both side" => L15 - 14L = (14T + 2) - 14L "Commutative multiplication" => L15 - L14 = (14T + 2) - 14L "Commutative multiplication" => L(15 - 14) = (14T + 2) - 14L "Factorize" => L*1 = (14T + 2) - 14L "Subtraction" => L = (14T + 2) - 14L "Multiplication" => L = (2 + 14T) - 14L "Commutative addition" => L = 2 + (14T - 14L) "Associative addition" => L = (14T - 14L) + 2 "Commutative addition" => L = (7*2T - 14L) + 2 "Multiplication" => L = ((7*2)T - (7*2)L) + 2 "Multiplication" => L = (7*(2T) - (7*2)L) + 2 "Commutative multiplication" => L = (7*(2T) - 7*(2L)) + 2 "Commutative multiplication" => L = 7(2T - 2L) + 2 "Factorize" Let H = (2T - 2L), then H is an integer since: 2 and T are integers => 2T is an integer "closure" 2 and L are integers => 2L is an integer "closure" 2T and 2L are integers => 2T - 2L is an integer "closure" => L = 7H + 2 "Substitution" => L = 2 (mod 7) "Definition of mod"

[@NotYourAverageNothing]

You don’t have to do that mess, and can just use modular substitution. Since 15 ≡ 1 (mod 7), 15 can be substituted with 1.

[@rb1471]

Not Your Average Nothing As I mentioned before, this is to show the magic behind: "Since 15 ≡ 1 (mod 7), 15 can be substituted with 1."

[@sushi_1233]

Thank you SO much! THIS ACTUALLY HELPED ME!!! And the fact that I only needed to watch the video once to understand this, it shows that you're great at explaining things!

[@akolangto8225]

What I want for this channel is Sir Steve is not a boring teacher when he lectures, and always keep smiling. From the philippines here

[@darshankrishnaswamy4520]

YOU REACHED 100K SUBS! Congrats!

[@blackpenredpen]

Darshan Krishnaswamy thank you!!!!

[@VerSalieri]

I love those. Although, when tutoring my students for university entrance exams, i used to tell them to go with trial and error (just try out all but one of the choices till one fits). But I love solving them, really enjoyed that. Thanks.

[@CrazyMrCritic]

This makes way more sense now! I learnt this as a formula that made no sense. Thank you for this!

[@bengper8044]

I can't believe how well this was explained! Thank you so much!!

[@Jeff-wc5ho]

I recently purchased a subscription to Brilliant as per your advice, and I'm loving it! Thanks so much for sharing these wonderful puzzles with us :)

[@logio7663]

You are so good at explaining, looking forward for more videos ;D

[@alobaidicommittee5921]

The passion in this mans voice resparks my love for math

[@urlikskull1071]

Why's no one talking about the Doraemon theme at the start

[@bakirhaljevac3584]

You have no idea how much you help me out, thank you

[@rithvikmuthyalapati9754]

You are one of the few KZbinrs I watch whose sponsor segments are worth watching.

[@mryip06]

Last 2 equation give x ≡ -1 (mod5) x ≡ -1 (mod7) and therefore x ≡ -1 (mod 35) x = 35k -1 35k -1 ≡ 1 (mod3) 35k ≡ 2 (mod3) 2k ≡ 2 (mod3) k ≡ 1 (mod3) k = 3m+1 x = 35(3m+1)-1=105m+34

[@epic2232]

OMG!! This was SOOO useful. Thank you so much!!

[@kellywu4467]

This was so informative. Thank you so much!! You made it clear on how to do it but I wish there was just a few more explanations on the modular arithmetic rules. Thank you nonetheless. Well done. Thanks so much!

[@blackpenredpen]

Do you have any specific problem that you would like me to work out?

[@RexxSchneider]

When the system contains small numbers for the mod (like 3), you can often take a short-cut. Whatever solution we have for these sort of systems, we can always generate another solution by adding or subtracting the product of the modulo bases, in this case 3 x 5 x 7 = 105. Hopefully, that is self-evident, since 105 congruent 0 (mod 3 or mod 5 or mod 7). So if a solution exists, it has to be between 0 and 105. Also note that in this problem 4 congruent -1 (mod 5) and 6 congruent -1 (mod 7). That means that -1 satisfies the second and third congruencies, as does -1 + 35n where n is an integer. Since we only need examine the range 0 to 105, we only need to look at 35 -1 and 70 -1 to see if they satisfy the first congruence. Of course, 34 does. The small amount of work necessary is because 3 is such a small number, so we only need to look a two possibilities in the range.

[@Rudxain]

I had a similar solution: cong 1 mod 3 means "1 more than some multiple of 3" and cong 4 mod 5 and cong 6 mod 7 both mean "1 less than some multiple of 5, and 1 less than some mult of 7". We can merge the last 2 equations into cong 34 mod 35 (1 less than some multiple of BOTH 5 AND 7), then check if 35-2 is cong 0 mod 3, in this case we got the correct answer at 1st try! So just add 1 to 33 and x = 34

[@Energya01]

Thanks for helping me solve AdventOfCode day 13!

[@pixel6090]

100k subs bro big family. Congrats!

[@blackpenredpen]

Tufan thank you!!

[@Nachc18]

Excellent video!! Thank you for teaching different areas of math. Is this topic related to divisibility?

[@raysun1681]

Nice video, you somehow make math fun enough for me to learn it. nice explanation.

[@julian803]

Here's another quick method to answer this question. The first congruence 1 ( mod 3 ) can be changed to 4 (mod 3) since 1 and 4 are congruent mod 3. By the Chinese Remainder Theorem, the first congruence 4 ( mod 3 ) and second congruence 4 ( mod 5 ) can be rewritten as 4 ( mod 15 ). 4 ( mod 15 ) can be rewritten as 34 ( mod 15 ) since 4 and 34 are congruent mod 15. Then the last congruence 6 ( mod 7 ) can rewritten as 34 ( mod 7 ) since 6 and 34 are congruent mod 7. By the Chinese Remainder Theorem, 34 ( mod 15 ) and 34 ( mod 7 ) is equivalent to 34 ( mod 105 ). Any integer of the form 105m + 34 satisfies the system of congruences just like you said. Thanks for the videos!!

[@emaadhakeem9856]

If you want to learn more about the CRT, try going for the bezout's identity and the extended euclidean algorithm (which is used to find the bezout's identitiy).

[@youngzproduction7498]

Your vid saves my life. Thanks

[@scarlettwang2643]

Thank u man, this helps my assignment

[@aashabulimam2608]

well explained! thank you

[@blackpenredpen]

You're welcome!

[@delealli9965]

This is so great. thank you dude

[@blackpenredpen]

Happy to help : )

[@cryodrakon]

How I think it would be more simple: If x=4=-1 mod 5 and x=6=-1 mod 7, we have that 5 and 7 divides x+1. Knowing that, we also have that 35 divides x+1, so we can write x+1=35k, for some natural number k. Looking x=35k-1 modulo k, we get x=2k-1 mod 3 and we have to have x=1 mod 3, so we have 2k-1=1 mod 3, so 2k=2 mod 3. It's easy to see that for k=1 it's true, and k=1 is the smalles value for which x is positive. So x=35*1-1=34 is the solution!

[@PBJJJ]

this was suuupppeeerrrr helpful, thank yooooouuuu 😄😄😄

[@leonardo_magallanes]

Thank you so much, this video helped me a lot to understand this topic.

[@henrykoplien1007]

Nice solution.

[@denniscarambot4304]

good video, very helpful!!!

[@benjaminoseitutu7230]

This has really helped me

[@chigozie123]

Thanks a lot dude. You are saving lives, you don't even know it

[@amerendrakumar8087]

Congrats brother you've crossed 0.1+ million subscriber And nearly you can increase it to 1 and more... 💐💐💐💐💐💐💐👍👍💐💐💐

[@blackpenredpen]

Amerendra Kumar thank you!!!

[@TheMauror22]

You should prove the Chinese reminder theorem because I never understood the proof hahahahaha. Btw, congratulations for reaching 100k subs! I've been here since before you reached 10k!

[@louiswouters71]

I don't know which part you didn't understand but the most important part is this. We add 3 things together, ax5x7 + bx3x7 + cx3x5. Why? Because whatever values we choose for a b c, the first term is 0 mod 5 and 0 mod 7 etc. This means that looking at solving for 1 mod 3 we only have to worry about the value of a and we are not messing up the other requirements. Therefore ax5x7=1 mod 3 35a=1 mod 3 2a=1 mod 3 a=2 Let me know if you need more clarification. Once you understamd why it works it becomes easy to remember as well.

[@JM-us3fr]

The Chinese Remainder Theorem is best proven in Abstract Algebra. It becomes equivalent to finding an explicit isomorphism between certain groups, which is surprisingly straight forward.

[@user-bv8bd5np5i]

Nice explanation, i understand chinese remainder theorem using your lemma and proof.

[@hajiro.7984]

thank you u helped me a lot

[@jack-jt2lm]

great explaining ,thx

[@DanielSColao]

Thanks! Great video

[@ethann8827]

Love this!

[@satadrubanerjee4862]

Damn thanks a lot!!! This was really helpful!! Stuck in quarantine due to corona virus thing and stuck with Chinese remainder theorem too xD!! Helped a lot!!❤️

[@user-ef6fg2xn8k]

OMG! thank u so much

[@gen3360]

Our sir gave us a similar question to this, which came in a previous RMO paper and it goes as follows : Find the smallest x for which : x is congruent to 2(mod4) x is congruent to 3(mod5) x is congruent to 1(mod7) The trick is here deriving a relation between k1, k2 and k3 by equating all of them by expressing them all in x-b=kz form. Soln : by deriving a relation between k1 and k2 we see that that k1= 5n and k2 = 4n where n is an int, using this we can also equate k1 and k2 to k3, by expressing the third expression in the form x-2 = 7k3 - 4 And then finding k3.

[@maguszedrin4793]

Great video thank you.

[@UltraLuigi2401]

It has to be in the forms 3n+1, 5n-1, and 7n-1. The second two mean it has to be in the form 35n-1. Since we're looking for the smallest, it shouldn't take too long to try all of them. 34, being 35(1)-1, happens to also be 3(11)+1. That was easy.

[@sadinenivijayasanjeevi5341]

nice

[@sadinenivijayasanjeevi5341]

nice

[@KGBedg7]

wondeful ! tanks!!!

[@JoseHernandez-fk3jz]

Best youtuber of 2018

[@sanjibbehera1]

Thank you

[@BrikaEXE]

Better video ever covering chinese remainder system, all talk about using bézout theorem and getting inverse mod something kinda, but its hard and beyond 2 congruences it becomes a mess , thank u so much

[@bekahresendez7021]

yay! thank you!

[@aiden_420]

Thank you very much 🤗

[@blackpenredpen]

: )

[@allaboutstat1103]

Excellent 👍 thanks 😊 I can answer now❣️

[@soumyachandrakar9100]

Congratulations! on getting 100K+ subscribers......

[@blackpenredpen]

Soumya Chandrakar yay!!!! Thank you!!

[@ObitoSigma]

I absolutely love number theory!

[@AjayPatel-te4kb]

amazing bro..keep it up

[@JashanTaggar]

Can you make videos relating to Linear Algebra topics? That'd be awesome.

[@mathsforlife5484]

Hi blackpenredpen, could you make a video making a video about geometry proofs? Thank you!

[@samratmukherjee992]

in the last bit, a little explanation related to multiplicative inverse was required.. while you were deriving relation related to L

[@wameireagan635]

I like the way you teach bro

[@KnakuanaRka]

Great discussion of the Chinese Remainder Theorem, but one thing’s missing. During the two steps you did here, you were able to easily simplify the two mod equations you got; the first one easily let you divide out 3, while the second one let you easily mod away the 15 to get 1. What is the more generic way to solve these mod equations? For example, in the example you gave, imagine omitting the second one. After you plug 3k+1 into the third mod, you get 3k=5 mod 7. Is there any way simpler than trial and error to solve this equation for k=4 mod 7?

[@siddharthsambamoorthy4479]

Excellent video...do more of number theory

[@mryip06]

Thanks

[@vonneumann3592]

Sir , please keep uploading videos on number theory concepts

[@kinyutaka]

4 mod 5 and 6 mod 7 are both one below their mod, therefore you can multiply 5 and 7 to make 35. Plug in 35k-1 to 1 mod 3. Add the +1 on each side and you get 35k being 2 mod 3. K=1 satisfies 2 mod 3 as well, therefore x = 33+2-1 or 34.

[@johi5951]

HAPPY 100K U DESERVED IT MAN! FOLLOWING U SINCE 10K for real though, i've learnt a lot of al-jabr, calculus and how to think in general with ur videos. Love the content. Keep it up. Greetings from chile. Grande chile jiji viendo esta wea cuando deberia estar estudiando historia jijiji pero grande bprp

[@blackpenredpen]

Jo Hi thank you!!!!!!!!!

[@Filip-pd5zc]

You hit 100k subscribers gj !!!!

[@blackpenredpen]

Tudi Gaming yay!! Thank yoy

[@Sitanshu_Chaudhary]

Please make video on chinese remainder theorem

[@Koisheep]

When I was in college our teacher simply dropped the general formula without explaining how to get it. To think it was so clear

[@plislegalineu3005]

I did it like that: x --- 1 (mod 3) x --- 4 (mod 5) x --- 6 (mod 7) from first one I see it is also --- 4, and because the first two numbers in brackets are co-prime, I combined both to x --- 4 (mod 15) I created an equation 15k + 4 = 7l + 6 and by trial and error I got k=2, l=4, so x=34

[@alipourzand6499]

Great! 15k + 4 = 7l +6 gives 15k - 7l = 2 which is a Bézout identity meaning that gcd(k, l) = 2. So smallest k and l would be 2 and 4.

[@Galileo2pi]

Cool, thanks

[@Jo-Bailen]

Hi. May i ask what activity with manipulatives can i use to introduce this topic? Your help will be highly appreciated. Thanks.

[@faizanurrehman6220]

Awesome work bro,but can you make more video's on gcd and (mod).?

[@niklasmaier2664]

Congrats in 100k!

[@blackpenredpen]

Niklas Maier thank you!!

[@osnapitzkaan]

I've just started this topic in my Further Maths class and these videos are very useful. Thank you so much! Keep up the good work :)

[@blackpenredpen]

Yay!!!

[@wonhyuk4]

I am a university student in Korea. You gave me great help for my math exam. Thank you for your effort. Keep hustling!! You used a bluepen in this video lol😂

[@inalambricoteseo3082]

Thank you profesor for your excellent videos. What about systems of congruences with no coprime modules,? do exist equivalent theorem to chinese remainders theorem,? could you explain it please,,?

[@davidbrisbane7206]

I used *_try & check_* to solve this problem. This approach is heuristically faster than the analytic approach when the modulos are small and quite close to each other in value like 3,5 and 7 are. I started with the biggest modulo. I.e the last congruence equation and tried x = 6, 13, 20, 27 and then x = 34. This last value satisfies the three congruences (easily check in ones head). We can stop looking at other values of x, as the CRT guarantees there is one and only one solution to the congruence equations. So, I then multiplied 3 × 5 × 7 to get 105. This works because 3,5 and 7 are relatively prime (they don't need to be prime, but if they are, then they are also relatively prime). So if x = 34 satisfies the congruence and then so too does x = 34 + 105k, where k is an integer and as 3 × 5 × 7 = 105. So, x = 34 (mod 105) is the general solution.

[@aleksasekulic2133]

Nice video 👍

[@juandelacruz9125]

Can you talk about modal arithmetic? I don't anything about this topic, please. Thank you for all your videos.

[@holyshit922]

With extended Euclidean algorithm - we need only two iterations We must have pairwise coprime modules then we need only n-1 iterations I guess it is O(nlogn) complexity First iteration 1=3*(2)+5*(-1) x = (3*2*4 + 5*(-1)*1) (mod 15) x = 19(mod 15) x = 4(mod 15) Second iteration x = 4(mod 15) x = 6(mod 7) 1 = 15*1+7*(-2) x = (15*1*6 + 7*(-2)*4)(mod 105) x = (90 - 56)(mod 105) x = 34 (mod 105)

[@razvanrusan9319]

I'm super glad I figured this out on my own! This modular arithmetic stuff is super easy for me (well, at least these basics, I'm sure there is Olympiad level stuff that will screw me over :p). Does anyone have any slightly harder modular arithmetic problems or puzzles?

[@y.z.6517]

Do a course on number theory.

[@NotYourAverageNothing]

I laughed way harder than I should’ve (even saw the joke coming) at 1:24.

[@jwm239]

...and note that after the smallest such integer, there is an infinite series of greater integers with same property....and the common difference between each is the LCM, in this case, of 3, 5, and 7.

[@msbinoovikashyadav9647]

Too much sir for your time and consideration

[@HaitaoWang268]

200k subscribers now!

[@angeloritofasanaro9850]

Your lessons about operational calculus superlative in the discret and in the continous compared with analogie transformer and anti

[@aidenlim5901]

For this one, here's what I did (before he did the problem of course). I said - Look for integer x, which means that 1 - x = 3a+1 = 5a+4 = 7c+6. - This means that 2 - (x-1)/3 = a 3 - (x-4)/5 = b 4 - (x-6)/7 = c - I can now conclude that x has to be at least 13. - Because of my limited knowledge of number theory, I made 3 lists of possible values for x based on each equation. a = 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46, 49, 52, 55, 58, 62, ... b = 14, 19, 24, 29, 34, 49, 44, 49, 54, 59, 64, 69, ... c = 13, 20, 27, 34, 41, 48, 55, 62, 69, .... - I then looked for the Least Common Multiple, which was 34. - Double checking, each equation results in 1 - 34 = 34 = 34 = 34 2 - a = 11 3 - b = 6 4 = c = 4 "The good old algebra days." - bprp

[@haydergfg6702]

good thx alot

[@zhangruoran]

I have a feeling that we taught the same course :D

[@kokainum]

Well explained. Although I wonder isn't it easier to start from largest devisor (which is 7 here) and then go to smaller ones. Shouldn't we get smaller numbers cause we are casting onto smaller fields?

[@DilipKumar-ns2kl]

A general equation for the minimum number which gives remainders a,b,c when divided by 3, 5,7 can be written as below. N=70a+21b+15c + or - 105n, Where n = 0,1,2,3....... 'n' can be chosen in such a way that 'N' becomes minimum. Obviously N is the required number for the given remainders a,b,c. Congrats for system of congruences and solution.

[@DilipKumar-ns2kl]

A shortcut to CRT!

[@leeya675]

resolve congruent system x congruent1(mod6) , x congruent5(mod14) , x congruent4(mod21)

[@anonymic79]

I don't know if I fell through a gap in school but modular mathematics and any math involving matrices were not presented during a relatively standard mathematics path in HS. However, students in less advanced classes, thye seemed to be a core of at least a year of their math carreer in HS. It was very strange being near top of advanced math classes and completely lost when asked for help by other students. Hopefully that picture has changed because they are very useful ideas in later mathematics.

[@elchingon12346]

I'm taking number theory in the summer, I'd love to see the proof for division in modular arithmetic

[@ObitoSigma]

"Division in modular arithmetic" is known as the "Cancellation Law" in algebra where ax≡ay implies that x≡y as long as a!≡0. I endorse +VeryEvilPettingZoo for having an excellent set of propositions derived from the very foundations of ring theory.

[@kantaprasadsinha8025]

U r requested to see Aryabhattiya of Arya hatta . 476 AD b in India.It is called kuttaka. The sanskrit word means breaking into pieces. However ,name was given Kuttara patthodhoti by Bhaskarcharya1 , He was commentator of Aryabhatta1. U will get it Arya bharatiya bhashya.Both the book can be available in Internet Achieve in Sanskrit with English Translation

[@karlaguilar5212]

Liked the Video for Simply saying thank you!