Number Theory | Chinese Remainder Theorem: Example 2

Рет қаралды 17,215

Күн бұрын

Пікірлер: 29

@aahpandasrun 3 жыл бұрын

You're literally THE ONLY person on youtube who can explain this well. Everyone dives into examples but never tells you the steps, why they're doing it, or where numbers come from. Thanks so much!

@georgesadler7830 3 жыл бұрын

Professor Penn ,thank for explaining The Chinese Remainder Theorem by example.

@spiderjerusalem4009 2 жыл бұрын

what proof? That was a mere basic exercise just as prior

@PunmasterSTP 3 жыл бұрын

Another wonderful video; thanks for posting!

@sarahramalho5085 9 ай бұрын

Hey,Michael. In 35x2 equivalent to 1 (mod6), don ´t X2=7 instead of 5, because i did not find 25 in the modular numerical line of 1 (mod6), i just found 35 . 1(mod6) = ... -31 -25 -17 -11 -5 0 7 15 21 27 35 ....

@sambernardo9907 3 жыл бұрын

How did you reduce 42 to 2, 35 to 5, and 30 to 2?

@paulmialane3994 3 жыл бұрын

I'll use "=" as "congruent" If ab=c (mod n) and a=d mod(n) then you can replace the a by a d! So you end up getting ab=c (mod n) db = c (mod n). Here, you can see that 42=2 (mod 5), so you get 42X=1 (mod 5) 2X=1 (mod 5). And he does this for 35 and 30 as well! Notice that reducing shouldn't change the final solution at all. It is just easier to deal with the smallest numbers you can if you don't have a calculator! I hope it was clear enough

@spiderjerusalem4009 2 жыл бұрын

you can modulo both the LHS and RHS.

@Laura-hs1rs 11 ай бұрын

I don't get it

@aditighuge3256 2 ай бұрын

Is it correct?

@davidbrisbane7206 3 жыл бұрын

Now, if you like a challenge, try to solve x = 17 (mod 119) x = 47 (mod 241) x = 14 (mod 200) I suggest you *don't* use guess and check, as the smallest x satisfying all three congruence equation is larger than one million.

@simonelicciardi114 3 жыл бұрын

I tried it. I arrived to a point where i knew 34|x, and had a system with 2 (horrible) congruences. Tbh idk how to proceed... I suppose it is meant to develop into something = 0 so that we get the answer by using the factorization. Is it?

@davidbrisbane7206 3 жыл бұрын

@@simonelicciardi114 I wrote the solution down, but I don't have it with me now. As I remember, I think I used the full Chinese Remainder theorem but I have another way of solving it too, which is probably just the CRT unmasked. I'll look it up in a bit. I think it was quite long, but I can at least give you the answer soon.

@simonelicciardi114 3 жыл бұрын

If you wish, send it to Simone.mark@gmail.com :)

@davidbrisbane7206 3 жыл бұрын

@@simonelicciardi114 My answer is x ≣ 1,804,414 (mod 5,735,800) I checked it by hand for x = 1,804,414 against the three congruence equations, so hopefully this answer is correct. ... and yes, 34 | 1,804,414. I didn't check it in general for x = 1,804,414 + 5,735,800k, where k ∈ ℤ. I only check for the case k = 0. I did used the CRT in this example and I had to use the Euclidean Algorithm to find the multiplicative inverses of N₁, N₂ and N₃. N₁y₁ = 1 (mod 119) Where N₁ = 48,200 (mod 119) ⇒ y₁ = 24 (mod 119) N₂ y₂ = 1 (mod 241) Where N₂ = 23,800 (mod 241) ⇒ y₂ = 49 (mod 241) N₃y₃ = 1 (mod 200) Where N₃ = 28,679 (mod 200) ⇒ y₃ = 119 (mod 200) I have another method that doesn't use the CRT. What the other method does is finds a congruence equation solution (call this Equation C for combined solution) for the first two equations. Then I solve Equation C and the 3rd equation. This approach also seems to generate the correct answer to a system of linear congruence equations.

@davidbrisbane7206 3 жыл бұрын

@@simonelicciardi114 Ok. When I have time, I'll take a photo of the complete solution and put it in a pdf and email it to you 😁.

@snipergranola6359 4 жыл бұрын

How to know that , whether system is solvable or not

@MichaelPennMath 4 жыл бұрын

If the system satisfies the hypothesis of the CRT then there is always a solution. If it doesn't, then you need to do some tricks to put it in the right form -- these tricks will vary depending on the specific system.