20100217, 20:07  #1 
Sep 2004
533_{10} Posts 
solving modular constraints
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. 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! 
20100217, 20:51  #2  
Nov 2003
2^{2}×5×373 Posts 
Quote:
You answered your own question. Use the CRT. What else are you looking for? There are plenty of examples. 

20100217, 20:55  #3 
"William"
May 2003
New Haven
23×103 Posts 
(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. 
20100217, 20:56  #4 
Jun 2003
The Texas Hill Country
3^{2}·11^{2} Posts 
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 
20100218, 07:56  #5  
Sep 2004
13·41 Posts 
Quote:


20100218, 13:04  #6  
Jun 2003
The Texas Hill Country
441_{16} Posts 
Why don't you tell us? Is it, or is it not? Why?
Quote:
Quote:
Quote:


20100219, 06:53  #7 
Sep 2004
13·41 Posts 
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? 
20100219, 06:56  #8 
Sep 2004
13×41 Posts 

20100219, 08:04  #9 
"William"
May 2003
New Haven
23×103 Posts 
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 =(40 mod 3) + (30 mod 3) + (48 mod 3) 
20100219, 15:24  #10  
Jun 2003
The Texas Hill Country
3^{2}·11^{2} Posts 
Quote:
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 X = 5 A + 3 This transformed the last constraint into Code:
5 A + 3 == 3 mod 5 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:
Find the set of integers "A" such that 2 A == 1 mod 3 and A == 3 mod 4 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:
X == 58 mod 60 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" Last fiddled with by Wacky on 20100219 at 15:52 Reason: Formatting to clarify the presentation 

20100219, 21:10  #11  
Sep 2004
533_{10} Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Solving for x in Phi(n, x) = 0 (mod p)  carpetpool  Abstract Algebra & Algebraic Number Theory  1  20171104 16:53 
Solving x^2 + x + 1 == 0 (mod mp)  paulunderwood  Miscellaneous Math  17  20161231 22:11 
Solving x^2==1 (mod n)  paulunderwood  Miscellaneous Math  2  20161230 07:34 
New Method for Solving Linear Systems  Dubslow  Miscellaneous Math  24  20120824 10:46 
Solving modular equivalence problems  flouran  Math  4  20081219 17:22 