- **Homework Help**
(*https://www.mersenneforum.org/forumdisplay.php?f=78*)

- - **solving modular constraints**
(*https://www.mersenneforum.org/showthread.php?t=13097*)

solving modular constraintsx = 1 mod 3
x = 2 mod 4 x = 3 mod 5 so I changed the numbers from my problem, but its similar. I'm trying to find what x could be. I'm pretty sure I can do LCM of 3,4,5 and know the answer is 60N + something or something mod 60. What's the best way to find out; for small problems it would seem try 8 then 13, and so on up to 60, is there a faster way for even small problems like this? I know there's fast ways using chinese remainder theorem; maybe someone could demonstrate a little algorithm on these numbers? Thanks! |

[QUOTE=Joshua2;205936]x = 1 mod 3
x = 2 mod 4 x = 3 mod 5 so I changed the numbers from my problem, but its similar. I'm trying to find what x could be. <snip> I know there's fast ways using chinese remainder theorem; ![/QUOTE] ?? You answered your own question. Use the CRT. What else are you looking for? There are plenty of examples. |

(40 + 30 + 48) mod 3 = (1+0+0)
(40 + 30 + 48) mod 4 = (0+2+0) (40 + 30 + 48) mod 5 = (0+0+3) so 40 + 30 + 48 = 118 works. As you have observed, any equivalent answer mod 60 will work. Depending on your needs, the smallest answer is either 58 or -2. As you seemed to already know, this is the Chinese Remainder Theorem. The trick is to make a sum so that all but one addend is zero for each modulo. I have difficulty imagining anything simpler. It's also more help than we ought to give in homework. I justify it on the grounds of your claim to have changed the numbers and the usefulness of a pedagogical example. |

Rather than "trying" 3, 8, 13, etc., do it algebraically.
If x = 3 mod 5, then x= 5A+3 for some integer A. Substituting in the other constraints 5A+3 = 1 mod 3 5A+3 = 2 mod 4 But this is the same as 2A = 1 mod 3 A = 3 mod 4 Thus, we have reduced the number of constraints. When we find permissible values for A, we can substitute and we will have the permissible values for x |

[QUOTE=Wacky;205945]Rather than "trying" 3, 8, 13, etc., do it algebraically.
If x = 3 mod 5, then x= 5A+3 for some integer A. Substituting in the other constraints 5A+3 = 1 mod 3 5A+3 = 2 mod 4 But this is the same as 2A = 1 mod 3 A = 3 mod 4 Thus, we have reduced the number of constraints. When we find permissible values for A, we can substitute and we will have the permissible values for x[/QUOTE] This way makes a ton of sense. Is this the CRT as well? Its seems we can't continue with 2A = 1 + 3A and A = 3 + 4A? I think I did that wrong. How about A = 3 + 4B and 2A = 1 + 3 B with two equations and two unknowns? I'll look at the other posts more later. |

[QUOTE=Joshua2;205976]Is this the CRT as well?[/QUOTE]
Why don't you tell us? Is it, or is it not? Why? [QUOTE] Its seems we can't continue with 2A = 1 + 3A and A = 3 + 4A? I think I did that wrong.[/QUOTE] A correct observation. [QUOTE]How about A = 3 + 4B and 2A = 1 + 3 B[/QUOTE]That's the spirit[QUOTE] with two equations and two unknowns?[/QUOTE]Is that what we did before? |

1. I don't think it is CRT, because I read that you use euclid's extended algorithm, and we didn't use it.
2. I think that is what we did before, reduce by one. A = -2 - B = 3 + 4B so -2 - 3 = 5B or -5 = 5B so B = -1. So is that the right idea? |

[QUOTE=wblipp;205944](40 + 30 + 48) mod 3 = (1+0+0)
(40 + 30 + 48) mod 4 = (0+2+0) (40 + 30 + 48) mod 5 = (0+0+3) so 40 + 30 + 48 = 118 works. [/QUOTE] Where did 40, 30 and 48 come from? I assume the 1+0+0 thing is prime factored? |

[QUOTE=Joshua2;206049]Where did 40, 30 and 48 come from?[/QUOTE]
CRT. The first number needs to be a multiple of 4*5 that is 1 mod 3. The second number needs to be a multiple of 3*5 that is 2 mod 4 The third number needs to be a multiple of 3*4 that is 3 mod 5 [QUOTE=Joshua2;206049]I assume the 1+0+0 thing is prime factored?[/QUOTE] (40 + 30 + 48) mod 3[INDENT]=(40 mod 3) + (30 mod 3) + (48 mod 3) = 1 + 0 + 0 =1[/INDENT] |

[QUOTE=Joshua2;206048]1.
2. I think that is what we did before, reduce by one. A = -2 - B = 3 + 4B so -2 - 3 = 5B or -5 = 5B so B = -1. So is that the right idea?[/QUOTE] No. I think that you may be confusing the "algebraic equality" (as in X = 5 A + 3) with the "modular equality" (as in X = 3 mod 5). They are somewhat different concepts. Therefore, for clarification, I will use "==" in the latter case. We are reducing the number of constraints by one by making a substitution that causes one of the constraints to be met for all values of the unknown. We started with: [CODE]Find the set of integers "X" such that X == 1 mod 3 and X == 2 mod 4 and X == 3 mod 5[/CODE] We made the substitution X = 5 A + 3 This transformed the last constraint into [CODE]5 A + 3 == 3 mod 5[/CODE] which is true for all integers A That left us with the equivalent problem: [CODE]Find the set of integers "A" such that 5 A + 3 == 1 mod 3 and 5 A + 3 == 2 mod 4[/CODE] or, equivalently: [CODE]Find the set of integers "A" such that 2 A == 1 mod 3 and A == 3 mod 4[/CODE] So, continuing this procedure: We let A = 4 B + 3 which will meet the last constraint for all integers B, leaving only one constraint (mod 3). Then we let B = 3 C + … (something), which will be true for all integers C. Finally, we combine all of the substitutions to get one substitution X = f(C), which meets all of the constraints for any integer C. As you already know, from other posts, this will be [CODE]X = 60 C + 58[/CODE] or equivalently, [CODE]X == 58 mod 60[/CODE] However, you should work out the details to derive the answer yourself. There are a couple of aspects of the derivation that might catch you unaware. You should also look to see similar coefficients in the CRT solution. Observing these similarities might give you a greater insight into "why the methods work" |

[QUOTE=wblipp;206056]CRT.
The first number needs to be a multiple of 4*5 that is 1 mod 3. The second number needs to be a multiple of 3*5 that is 2 mod 4 The third number needs to be a multiple of 3*4 that is 3 mod 5 (40 + 30 + 48) mod 3[INDENT]=(40 mod 3) + (30 mod 3) + (48 mod 3) = 1 + 0 + 0 =1[/INDENT][/QUOTE] I think I understand CRT now. Now I just need to figure out modulo inverses, like what is inverse of 2 mod 5... |

All times are UTC. The time now is 03:07. |

Powered by vBulletin® Version 3.8.11

Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.