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)
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).
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)."
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"
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.
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.
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
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!
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!!
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.
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
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.
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.
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.
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
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).
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.
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!
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!
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.
Here's a fun analytic way of solving this problem: We are looking for the smallest pos. integer that divides 3, 5, an 7 to get 1, 4, and 6. So: x is congruent to 1 (mod 3) x is congruent to 4 (mod 5) x is congruent to 6 (mod 7) we can rewrite this as: x = 3a + 1 x = 5b + 4 x = 7c + 6 Now here's where the fun begins. We know that multiples of 5 always end in 0 or 5. Meaning that x must end in either 4 or 9 once added by 4, because of the (5k + 4) stipulation. So we consider only multiples of 3 which end in 3 or 8, because (3k +1). We also consider only factors of 7 which end in 8 or 3 because of the (7k + 6) stipulation. So here we go: 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 42... 7, 14, 21, 28, 35, 42... Of the multiples of 3, just (3, 18, 33) remain. Of the multiples of 7, just (28) remains. Well 28 is our only candidate for 7 since 28 + 6 = 34. So let's see if x = 34. 34 = 33 + 1 34 = 30 + 4 34 = 28 + 6. We know that 34 is the smallest possible integer that can do this because we listed a set of multiples starting from least to greatest, so we are done, x = 34.
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
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😂
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!
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.
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.
I had a fun problem a couple of days ago, in my first course of life insurance. In the end, the problem comes down to differentiating an integral, where the variable is both in the limits of integration, AND in the integrand: U(t) = integral from 0 to t of exp( delta*(t-s) )* ( c(s) - b(s) ) ds Problem: Find U'(t) functions c(s) and b(s) are just treated as known functions. (money paid and recieved to/from the company). - then U(t) is the amount of money in your account if you receive continous rent, with delta (little delta) as the rate of rent. I have the answer if the challenge is too tough ;) Hope you will give it a try :)
actually we are not using a book, just 60 pages written by the lecturer :D. But it is just basic "interest rate theory" so i am sure there exist many books on this subject :) This integral comes up in "Continous interest and payments".
The reason for t being in both the limit and the integrand, is because when t grows, you pay over a larger time-interval - thus t being in the limits of integration. But as t grows, you will also have gained more interest from the money you have payed - thus t is also in the integrand :)
Here's an alternative proof also using the idea of Chinese Remainder Theorem without all the algebra: Let the smallest integer be n. We can write n as n=a+b+c, where a is congruent to 1 mod 3, b is congruent to 4 mod 5, and c is congruent to 6 mod 7, which is exactly the set of congruences that n satisfies. In order for their sum to satisfy this, we must make it so that a does not affect the congruence modulo 5 or 7, and likewise for b and c. To do this, we simply make them a factor of the other modulos. So a=5*7*x, b=3*7*y, and c=3*5*z. To see why, notice n*x is congruent to 0 modulo n, for any x. Furthermore, if we take the expression a+b+c modulo, say 3, we know the result is 1, and we also know that a is congruent to 1 modulo 3, so if b and c result in 0 modulo 3, 1+0+0=1, which works! Now, all that remains is to solve for x, y, and z to make the numbers congruent to their respective values after modding. For a, 5*7*x is congruent to 1 mod 3. Notice, 35 is congruent to 2 mod 3, and so the smallest x is 2. For y, 3*7*y is congruent to 4 mod 5. Notice, 21 is congruent to 1 mod 5, so y=4. Finally, 3*5*z is congruent to 6 mod 7. Notice, 15 is congruent to 1 mod 7, and so z=6. Putting this all together, we find that n=5*7*2+3*7*4+3*5*6=70+84+90=244. Now, as the Chinese Remainder Theorem stated, this is unique modulo 3*5*7=105, and so 244 is congruent to 34 modulo 105, and that is our smallest answer.
Oh! I just noticed another solution :O Notice, 4 mod 5 is congruent to -1 mod 5, and 6 mod 7 is congruent to -1 mod 7. Thus, n+1 is divisible by both 5 AND 7, or it's divisible by lcm(5,7)=35, so smallest n to satisfy this is 35-1=34. Also, from n is congruent to 1 mod 3, we know that n-1 is divisible by 3. Checking 34, we see that 34-1=33 which IS divisible by 3. Thus our answer is 34.
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?
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)
...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.
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?
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.
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
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
I concluded that x-4 must be the multiplication of both 3 and 5. So I tried 15, 30... ect. Also (x-4)-2 is divisible by 7. So I got 30 -2 = 28. Then x=34. All in my head. I like these type of trick question 👍🏼 . The values are small enough that you can do trial and error, fast.
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.
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
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
As there are three coprime parameters: mod 3, mod 5, and mod 7, then if there is a solution, it will repeat every 3•5•7 = 105 integers. As there is a 4 mod 5, the answer will either end in 4 or 9. As there is a 6 mod 7, the answer will be one less than a multiple of 7, so let's start looking at multiples of 7 between 1 and 105 that end with 5 or 0, and then subtract 1. 105-1 = 104 = 2 mod 3 ❌ 70-1 = 69 = 0 mod 3 ❌ 35-1 = 34 = 1 mod 3 = 4 mod 5 = 6 mod 7 ✅ Therefore our solution is 34.
At 14:47 he solves the system of congruences but doesn't realize lol But to explain, he turned the variable x into l (little L), then solved for little L at 14:47, so all that was left was to plug in 2 for little L and out pops 34 as our answer. 15(2) + 4 = 34
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
@@muhammadumarfarooq7199 who cares? A method to solve a problem doesn't need to general. Especially considering there is no such thing as "all questions". Also, OP's reasoning IS the Chinese Remainder Theorem.
Look at this one: 6=10 (mod 4), but 3=/=5(mod 4), what if we divide 4 by 2 as well? then 3=5(mod 2), I checked for 14=6(mod 8) and 15=21(mod 6) and it indeed works, you just have to divide every single number in the equation by the greatest common denominator of all of them :)
this is how i did it. 5 rem 4 is 5 rem -1 7 rem 6 is 7 mod -1 so our required number is 35 mod -1 ie 34 plus something but 34 is 3n +1 as required so answer is 34
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?
I realized that the mod 5 would either end in 4 or 9. Then I went through multiples of 7 that would end in 5 or 0. The first such example is *34,* which fits all the criteria. Thinking about it a bit more I could have realized that the last two are both mod -1, which means I could just find the least common multiple of 5 and 7, then subtract 2 and see if that's divisible by 3. If not, then double the answer and try again, then triple, and so on.
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!!❤️
I actually solved it without pausing the video. I just realised x is congruent to 4 [mod5] and 6 [mod7]. In fact we can say x is congruent to -1 [mod5] and also -1 [mod7], which means x is congruent to -1 or 34 [ mod 5×7=35]. So we just need to find a number congruent to 1 [mod3] and 34 [mod35]. The smallest of which happens to be 34 itself.
I can't help thinking there must be an easier method. Could we use negative numbers? E.g., x ≡ 4 (mod 5) ≡ -1 (mod 5); x ≡ 6 (mod 7) ≡ -1 (mod 7); x ≡ -1 (mod 5 * 7) ≡ -1 (mod 35) ≡ 34 (mod 35). 34 = 3 * 11 + 1, so 34 ≡ 1 (mod 3), hence minimum x = 34. Admittedly, it's not very general, but it leads quickly to the correct answer.
Good job, but your last step was just guessing whether your x ≡ 1 (mod 3). There was a 25% that your answer would be congruent to 1 mod 3 since 5 and 7 were coprime would imply that x ≡ -1 (mod 35) would be 50% divisible by 3.
No, I didn't guess. As it happened, there was no need to do any more calculations, but it would have been easy to continue. The probability was actually 1 in 3 (just over 33%), not 1 in 4 (25%). If the first condition had been x ≡ 2 (mod 3), then x = 34 would not have satisfied that condition, as 34 ≡ 1 (mod 3). Adding 35 would have produced 69 ≡ 0 (mod 3). Adding another 35 would have produced 104 ≡ 2 (mod 3), which would have satisfied all the conditions. If the first condition had instead been x ≡ 0 (mod 3), it would have been sufficient to add 35 to 34, for an answer of 69.
This video went far too slowly for me personally, since all I needed was the concatenation of k, l, and m expressions. But I can see how it might be at a good pace for someone not familiar with the rest of the content. Anyway, it did show me a solution more formal than just trying out numbers from lists until you find the ones that work. :}
I got 139 which works but isnt the least😔 I found the LCM of 3,5, and 7 to be 105 so I knew I could divide 105 evenly by 3, 5, 7. Then I added 4 to guarentee I get a remainder of 1 for dividing by 3, and a reminder of 8 for 5, (4 being one greater than 3 guarantees the remainder will be 1 when added to multiple of 3, 4 being one less than 5 i.e. being .8 of 5 which means a remainder of 4 when added to a multiple of 5, 7 did not work so then I added 15 to preserve the remainders I got 3 and 5, 15 being the LCM of 3 and 5, I kept adding 15 until it worked for 7, I only needed to add two sets of 15 to get to 139 which worked for all of them but alas it wasn't the least Edit: I wrote gcf instead lcm, changed it, and cleared up some of my reasoning and logic
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,,?
Hey, there. I've got a question: Te system: 24x = 16 (mod 52) 36X = 4 (mod 28) it has the solution x =18 +91k, for any integer k. But 52 and 28 aren't co-prime numbers. SO why it has a solution?
You have to cancel out common factors from each side of the congruence and also from the divisor.when factor 4 is cancelled out from each side & the divisor,we get 6x=4 Mod(13) and 9x=1Mod(7) Solving it you get x=18 Mod(91) That is the same result as you have stated.
"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.
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)
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).
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)."
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"
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.
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."
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
Thanks
Thanks , i was struggling in that
what are the |'s?
@@felixfong2667 l was the letter he used in the video, it's a variable like x
Thanks alot :)
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.
Nice preview of the chinese remainder theorem.
You are one of the few RUclipsrs I watch whose sponsor segments are worth watching.
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.
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
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!
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!!
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.
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
This makes way more sense now! I learnt this as a formula that made no sense. Thank you for this!
The passion in this mans voice resparks my love for math
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.
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
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.
YOU REACHED 100K SUBS! Congrats!
Darshan Krishnaswamy thank you!!!!
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.
A shortcut to CRT!
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
Thanks for helping me solve AdventOfCode day 13!
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).
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.
nice
nice
I can't believe how well this was explained! Thank you so much!!
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!
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 :)
Why's no one talking about the Doraemon theme at the start
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!
Do you have any specific problem that you would like me to work out?
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.
Here's a fun analytic way of solving this problem:
We are looking for the smallest pos. integer that divides 3, 5, an 7 to get 1, 4, and 6.
So:
x is congruent to 1 (mod 3)
x is congruent to 4 (mod 5)
x is congruent to 6 (mod 7)
we can rewrite this as:
x = 3a + 1
x = 5b + 4
x = 7c + 6
Now here's where the fun begins. We know that multiples of 5 always end in 0 or 5. Meaning that x must end in either 4 or 9 once added by 4, because of the (5k + 4) stipulation. So we consider only multiples of 3 which end in 3 or 8, because (3k +1).
We also consider only factors of 7 which end in 8 or 3 because of the (7k + 6) stipulation.
So here we go:
3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 42...
7, 14, 21, 28, 35, 42...
Of the multiples of 3, just (3, 18, 33) remain.
Of the multiples of 7, just (28) remains.
Well 28 is our only candidate for 7 since 28 + 6 = 34. So let's see if x = 34.
34 = 33 + 1
34 = 30 + 4
34 = 28 + 6.
We know that 34 is the smallest possible integer that can do this because we listed a set of multiples starting from least to greatest, so we are done, x = 34.
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
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.
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😂
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!
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.
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.
I had a fun problem a couple of days ago, in my first course of life insurance.
In the end, the problem comes down to differentiating an integral, where the variable is both in the limits of integration,
AND in the integrand:
U(t) = integral from 0 to t of exp( delta*(t-s) )* ( c(s) - b(s) ) ds
Problem: Find U'(t)
functions c(s) and b(s) are just treated as known functions. (money paid and recieved to/from the company). - then U(t) is the amount of money in your account if you receive continous rent, with delta (little delta) as the rate of rent.
I have the answer if the challenge is too tough ;) Hope you will give it a try :)
Lauge Rønberg wow interesting! Are we assuming delta is a constant?
oh yes sry it is a constant :D
Lauge Rønberg I am also very interested in the application of this problem. Can you let me know what book are you using in your course?
actually we are not using a book, just 60 pages written by the lecturer :D. But it is just basic "interest rate theory" so i am sure there exist many books on this subject :) This integral comes up in "Continous interest and payments".
The reason for t being in both the limit and the integrand, is because when t grows, you pay over a larger time-interval - thus t being in the limits of integration. But as t grows, you will also have gained more interest from the money you have payed - thus t is also in the integrand :)
OMG!! This was SOOO useful. Thank you so much!!
Here's an alternative proof also using the idea of Chinese Remainder Theorem without all the algebra:
Let the smallest integer be n. We can write n as n=a+b+c, where a is congruent to 1 mod 3, b is congruent to 4 mod 5, and c is congruent to 6 mod 7, which is exactly the set of congruences that n satisfies.
In order for their sum to satisfy this, we must make it so that a does not affect the congruence modulo 5 or 7, and likewise for b and c. To do this, we simply make them a factor of the other modulos. So a=5*7*x, b=3*7*y, and c=3*5*z. To see why, notice n*x is congruent to 0 modulo n, for any x. Furthermore, if we take the expression a+b+c modulo, say 3, we know the result is 1, and we also know that a is congruent to 1 modulo 3, so if b and c result in 0 modulo 3, 1+0+0=1, which works!
Now, all that remains is to solve for x, y, and z to make the numbers congruent to their respective values after modding. For a, 5*7*x is congruent to 1 mod 3. Notice, 35 is congruent to 2 mod 3, and so the smallest x is 2.
For y, 3*7*y is congruent to 4 mod 5. Notice, 21 is congruent to 1 mod 5, so y=4.
Finally, 3*5*z is congruent to 6 mod 7. Notice, 15 is congruent to 1 mod 7, and so z=6.
Putting this all together, we find that n=5*7*2+3*7*4+3*5*6=70+84+90=244. Now, as the Chinese Remainder Theorem stated, this is unique modulo 3*5*7=105, and so 244 is congruent to 34 modulo 105, and that is our smallest answer.
Oh! I just noticed another solution :O
Notice, 4 mod 5 is congruent to -1 mod 5, and 6 mod 7 is congruent to -1 mod 7. Thus, n+1 is divisible by both 5 AND 7, or it's divisible by lcm(5,7)=35, so smallest n to satisfy this is 35-1=34.
Also, from n is congruent to 1 mod 3, we know that n-1 is divisible by 3. Checking 34, we see that 34-1=33 which IS divisible by 3.
Thus our answer is 34.
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?
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)
...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.
Best youtuber of 2018
You have no idea how much you help me out, thank you
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?
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.
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
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
resolve congruent system x congruent1(mod6) , x congruent5(mod14) , x congruent4(mod21)
I concluded that x-4 must be the multiplication of both 3 and 5. So I tried 15, 30... ect. Also (x-4)-2 is divisible by 7. So I got 30 -2 = 28. Then x=34. All in my head. I like these type of trick question 👍🏼 . The values are small enough that you can do trial and error, fast.
It's amazing...
It helps me alot in my exams❤
Thanks a lot dude. You are saving lives, you don't even know it
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.
You are so good at explaining, looking forward for more videos ;D
Congrats brother you've crossed 0.1+ million subscriber And nearly you can increase it to 1 and more...
💐💐💐💐💐💐💐👍👍💐💐💐
Amerendra Kumar thank you!!!
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
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
As there are three coprime parameters: mod 3, mod 5, and mod 7, then if there is a solution, it will repeat every 3•5•7 = 105 integers. As there is a 4 mod 5, the answer will either end in 4 or 9. As there is a 6 mod 7, the answer will be one less than a multiple of 7, so let's start looking at multiples of 7 between 1 and 105 that end with 5 or 0, and then subtract 1.
105-1 = 104 = 2 mod 3 ❌
70-1 = 69 = 0 mod 3 ❌
35-1 = 34 = 1 mod 3 = 4 mod 5 = 6 mod 7 ✅
Therefore our solution is 34.
At 14:47 he solves the system of congruences but doesn't realize lol
But to explain, he turned the variable x into l (little L), then solved for little L at 14:47, so all that was left was to plug in 2 for little L and out pops 34 as our answer. 15(2) + 4 = 34
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
Jo Hi thank you!!!!!!!!!
just do 3x5x7 = 105 then 105/3 = 35, 105/5 = 21, 105/7 = 15, add 35+21+15 = 71 then subtract 105 - 71 = 34 there youve got your smallest integer..
This method not apply for all question
@@muhammadumarfarooq7199 who cares? A method to solve a problem doesn't need to general. Especially considering there is no such thing as "all questions". Also, OP's reasoning IS the Chinese Remainder Theorem.
You are absolutely right. You way is THE way.
Look at this one: 6=10 (mod 4), but 3=/=5(mod 4), what if we divide 4 by 2 as well? then 3=5(mod 2), I checked for 14=6(mod 8) and 15=21(mod 6) and it indeed works, you just have to divide every single number in the equation by the greatest common denominator of all of them :)
100k subs bro big family. Congrats!
Tufan thank you!!
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 :)
Yay!!!
Nice explanation, i understand chinese remainder theorem using your lemma and proof.
this is how i did it. 5 rem 4 is 5 rem -1 7 rem 6 is 7 mod -1 so our required number is
35 mod -1 ie 34 plus something but 34 is 3n +1 as required so answer is 34
When I was in college our teacher simply dropped the general formula without explaining how to get it. To think it was so clear
this was suuupppeeerrrr helpful, thank yooooouuuu 😄😄😄
a ≡ b (mod c) Co modular
This is so great. thank you dude
Happy to help : )
Please make video on chinese remainder theorem
Congratulations! on getting 100K+ subscribers......
Soumya Chandrakar yay!!!! Thank you!!
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?
Do a course on number theory.
Can you talk about modal arithmetic? I don't anything about this topic, please. Thank you for all your videos.
This has really helped me
Your vid saves my life. Thanks
in the last bit, a little explanation related to multiplicative inverse was required.. while you were deriving relation related to L
Thank you so much, this video helped me a lot to understand this topic.
I realized that the mod 5 would either end in 4 or 9. Then I went through multiples of 7 that would end in 5 or 0. The first such example is *34,* which fits all the criteria.
Thinking about it a bit more I could have realized that the last two are both mod -1, which means I could just find the least common multiple of 5 and 7, then subtract 2 and see if that's divisible by 3. If not, then double the answer and try again, then triple, and so on.
Try the same with the bases 113, 181 and 197
well explained!
thank you
You're welcome!
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!!❤️
Nice video, you somehow make math fun enough for me to learn it. nice explanation.
Nice solution.
Thank you very much 🤗
: )
Thank u man, this helps my assignment
I actually solved it without pausing the video. I just realised x is congruent to 4 [mod5] and 6 [mod7]. In fact we can say x is congruent to -1 [mod5] and also -1 [mod7], which means x is congruent to -1 or 34 [ mod 5×7=35]. So we just need to find a number congruent to 1 [mod3] and 34 [mod35]. The smallest of which happens to be 34 itself.
Too much sir for your time and consideration
I can't help thinking there must be an easier method. Could we use negative numbers?
E.g., x ≡ 4 (mod 5) ≡ -1 (mod 5);
x ≡ 6 (mod 7) ≡ -1 (mod 7);
x ≡ -1 (mod 5 * 7) ≡ -1 (mod 35) ≡ 34 (mod 35).
34 = 3 * 11 + 1, so 34 ≡ 1 (mod 3), hence minimum x = 34.
Admittedly, it's not very general, but it leads quickly to the correct answer.
Good job, but your last step was just guessing whether your x ≡ 1 (mod 3). There was a 25% that your answer would be congruent to 1 mod 3 since 5 and 7 were coprime would imply that x ≡ -1 (mod 35) would be 50% divisible by 3.
No, I didn't guess. As it happened, there was no need to do any more calculations, but it would have been easy to continue. The probability was actually 1 in 3 (just over 33%), not 1 in 4 (25%). If the first condition had been x ≡ 2 (mod 3), then x = 34 would not have satisfied that condition, as 34 ≡ 1 (mod 3). Adding 35 would have produced 69 ≡ 0 (mod 3). Adding another 35 would have produced 104 ≡ 2 (mod 3), which would have satisfied all the conditions. If the first condition had instead been x ≡ 0 (mod 3), it would have been sufficient to add 35 to 34, for an answer of 69.
great explaining ,thx
This video went far too slowly for me personally, since all I needed was the concatenation of k, l, and m expressions. But I can see how it might be at a good pace for someone not familiar with the rest of the content. Anyway, it did show me a solution more formal than just trying out numbers from lists until you find the ones that work. :}
You like a lot of math you say? Don't suppose you could do a video teaching us something from category theory then?
What’s category theory?
@@azice6034 Category Theory is one hell of a mathematics module!!!
Faculty of Khan and Fematika have some cool videos on category theory.
Thanks! Great video
Great video thank you.
I absolutely love number theory!
Excellent video!! Thank you for teaching different areas of math. Is this topic related to divisibility?
I got 139 which works but isnt the least😔
I found the LCM of 3,5, and 7 to be 105 so I knew I could divide 105 evenly by 3, 5, 7. Then I added 4 to guarentee I get a remainder of 1 for dividing by 3, and a reminder of 8 for 5, (4 being one greater than 3 guarantees the remainder will be 1 when added to multiple of 3, 4 being one less than 5 i.e. being .8 of 5 which means a remainder of 4 when added to a multiple of 5, 7 did not work so then I added 15 to preserve the remainders I got 3 and 5, 15 being the LCM of 3 and 5, I kept adding 15 until it worked for 7, I only needed to add two sets of 15 to get to 139 which worked for all of them but alas it wasn't the least
Edit: I wrote gcf instead lcm, changed it, and cleared up some of my reasoning and logic
Thank you
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,,?
My discrete math classic skipped this. We only covered finding linear inverses.
Can you make videos relating to Linear Algebra topics? That'd be awesome.
good video, very helpful!!!
Thanks
Hi blackpenredpen, could you make a video making a video about geometry proofs? Thank you!
I like the way you teach bro
Hey, there. I've got a question:
Te system: 24x = 16 (mod 52)
36X = 4 (mod 28)
it has the solution x =18 +91k, for any integer k.
But 52 and 28 aren't co-prime numbers. SO why it has a solution?
You have to cancel out common factors from each side of the congruence and also from the divisor.when factor 4 is cancelled
out from each side & the divisor,we get
6x=4 Mod(13) and
9x=1Mod(7)
Solving it you get
x=18 Mod(91)
That is the same result as you have stated.
I'm taking number theory in the summer, I'd love to see the proof for division in modular arithmetic
"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.
V. V helpful. But at the end you said 0 is smallest positive integer. But it is not.
Oooh, look at those Brilliant sponsorships rolling in!!!