System of congruences, modular arithmetic

first 200 people to sign up will get 20% off your subscription, and you can also support my channel! Thank you!

10% off with the code "TEESPRINGWELCOME10"

Equipment:
---------------------------------------------------------------------------------------------------

[thiagoschnaider]

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.

[tdiaz]

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

[JalebJay]

Nice preview of the chinese remainder theorem.

[rb]

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)

[rithvikmuthyalapati]

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

[sushi_]

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!

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

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

[julian]

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

[akolangto]

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

[alobaidicommittee]

The passion in this mans voice resparks my love for math

[bengper]

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

[Energya]

Thanks for helping me solve AdventOfCode day 13!

[emaadhakeem]

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

[Jeff-wcho]

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

[genosingh]

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.

[kellywu]

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!

[mryip]

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

[davidbrisbane]

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.