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.

[@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."

[@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 :)

[@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

[@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!

[@urlikskull1071]

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

[@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 :)

[@darshankrishnaswamy4520]

YOU REACHED 100K SUBS! Congrats!

[@blackpenredpen]

Darshan Krishnaswamy thank you!!!!

[@logio7663]

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

[@bakirhaljevac3584]

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

[@epic2232]

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

[@alobaidicommittee5921]

The passion in this mans voice resparks my love for math

[@rithvikmuthyalapati9754]

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

[@raysun1681]

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

[@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?

[@leonardo_magallanes]

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

[@user-bv8bd5np5i]

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

[@Energya01]

Thanks for helping me solve AdventOfCode day 13!

[@pixel6090]

100k subs bro big family. Congrats!

[@blackpenredpen]

Tufan thank you!!

[@scarlettwang2643]

Thank u man, this helps my assignment

[@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.

[@youngzproduction7498]

Your vid saves my life. Thanks

[@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!!❤️

[@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!!!

[@PBJJJ]

this was suuupppeeerrrr helpful, thank yooooouuuu 😄😄😄

[@Nachc18]

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

[@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!!

[@chigozie123]

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

[@benjaminoseitutu7230]

This has really helped me

[@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).

[@jack-jt2lm]

great explaining ,thx

[@ethann8827]

Love this!

[@DanielSColao]

Thanks! Great video

[@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

[@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

[@hajiro.7984]

thank you u helped me a lot

[@denniscarambot4304]

good video, very helpful!!!

[@aashabulimam2608]

well explained! thank you

[@blackpenredpen]

You're welcome!

[@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😂

[@delealli9965]

This is so great. thank you dude

[@blackpenredpen]

Happy to help : )

[@maguszedrin4793]

Great video thank you.

[@user-ef6fg2xn8k]

OMG! thank u so much

[@henrykoplien1007]

Nice solution.

[@bekahresendez7021]

yay! thank you!

[@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.

[@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!!!!!!!!!

[@JoseHernandez-fk3jz]

Best youtuber of 2018

[@AjayPatel-te4kb]

amazing bro..keep it up

[@mathsforlife5484]

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

[@allaboutstat1103]

Excellent 👍 thanks 😊 I can answer now❣️

[@soumyachandrakar9100]

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

[@blackpenredpen]

Soumya Chandrakar yay!!!! 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!!!

[@ObitoSigma]

I absolutely love number theory!

[@JashanTaggar]

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

[@samratmukherjee992]

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

[@siddharthsambamoorthy4479]

Excellent video...do more of number theory

[@vonneumann3592]

Sir , please keep uploading videos on number theory concepts

[@KGBedg7]

wondeful ! tanks!!!

[@faizanurrehman6220]

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

[@Sitanshu_Chaudhary]

Please make video on chinese remainder theorem

[@Galileo2pi]

Cool, thanks

[@wameireagan635]

I like the way you teach bro

[@aiden_420]

Thank you very much 🤗

[@blackpenredpen]

: )

[@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

[@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

[@sanjibbehera1]

Thank you

[@Filip-pd5zc]

You hit 100k subscribers gj !!!!

[@blackpenredpen]

Tudi Gaming yay!! Thank yoy

[@mryip06]

Thanks

[@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?

[@juandelacruz9125]

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

[@aleksasekulic2133]

Nice video 👍

[@NotYourAverageNothing]

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

[@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.

[@angeloritofasanaro9850]

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

[@zhangruoran]

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

[@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.

[@haydergfg6702]

good thx alot

[@Jo-Bailen]

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

[@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?

[@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.

[@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!

[@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

[@HaitaoWang268]

200k subscribers now!

[@msbinoovikashyadav9647]

Too much sir for your time and consideration

[@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.

[@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!

[@NotYourAverageNothing]

My discrete math classic skipped this. We only covered finding linear inverses.

[@VaradMahashabde]

Oooh, look at those Brilliant sponsorships rolling in!!!

[@karlaguilar5212]

Liked the Video for Simply saying thank you!

[@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.

[@niklasmaier2664]

Congrats in 100k!

[@blackpenredpen]

Niklas Maier thank you!!

[@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.

[@wameireagan635]

Could you please do a complete course on further curve sketching in further maths plsss

[@AJMaths]

A-Level Further Maths?

[@oscaraguilar9743]

BPRP my friend and me are stuck on this problem, its a IMO's problem, exactly 3rd problem of 2017, that's very famous because was a really really hard problem, maybe it's not your kind of videos but if you can help us, i'll appreciate that a lot:D Problem 3. A hunter and an invisible rabbit play a game in the Euclidean plane. The rabbit’s starting point, A0, and the hunter’s starting point, B0, are the same. After n−1 rounds of the game, the rabbit is at point An−1 and the hunter is at point Bn−1. In the n th round of the game, three things occur in order. (i) The rabbit moves invisibly to a point An such that the distance between An−1 and An is exactly 1. (ii) A tracking device reports a point Pn to the hunter. The only guarantee provided by the tracking device to the hunter is that the distance between Pn and An is at most 1. (iii) The hunter moves visibly to a point Bn such that the distance between Bn−1 and Bn is exactly 1. Is it always possible, no matter how the rabbit moves, and no matter what points are reported by the tracking device, for the hunter to choose her moves so that after 109 rounds she can ensure that the distance between her and the rabbit is at most 100?

[@Apollorion]

Well, how about assuming that rabbit & hunter are not super smart and don't use their memory but instead behave like this: 1) the rabbit always jumps strait away from the hunter. 2) the hunter always goes strait in the direction of the tracking device In such a situation, if Dn-1 is the distance between the rabbit and hunter after n-1 rounds, then we can derive that Dn^2 is at most (Dn-1)^2+1/((Dn-1)+1). And this in combination with D0=0 might be enough to begin a proof to what's necessary. .. and posting this comment will hopefully keep me informed.

[@Apollorion]

continuing.. since Dn-1 is a distance, it is greater than or equal to 0, and thus 1/((Dn-1)+1) is equal to or smaller than 1, but bigger than 0. And thus, Dn^2 is smaller than or equal to (Dn-1)^2+1. And thus, since D0=0, Dn^2 is smaller than or equal to n. And thus (D109)^2 is smaller than or equal to 109 and thus D109

[@azice6034]

This question is so detailed and hard I remember going over this and it completely going over my head lol I just had to knod and pretend I understood what my prof was trying to say

[@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