mersenneforum.org solving modular constraints
 Register FAQ Search Today's Posts Mark Forums Read

 2010-02-17, 20:07 #1 Joshua2     Sep 2004 13×41 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!
2010-02-17, 20:51   #2
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by Joshua2 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 know there's fast ways using chinese remainder theorem; !
??

What else are you looking for? There are plenty of examples.

 2010-02-17, 20:55 #3 wblipp     "William" May 2003 New Haven 1001001101102 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.
 2010-02-17, 20:56 #4 Wacky     Jun 2003 The Texas Hill Country 32×112 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
2010-02-18, 07:56   #5
Joshua2

Sep 2004

53310 Posts

Quote:
 Originally Posted by Wacky 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
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.

2010-02-18, 13:04   #6
Wacky

Jun 2003
The Texas Hill Country

32×112 Posts

Quote:
 Originally Posted by Joshua2 Is this the CRT as well?
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.
A correct observation.
Quote:
 How about A = 3 + 4B and 2A = 1 + 3 B
That's the spirit
Quote:
 with two equations and two unknowns?
Is that what we did before?

 2010-02-19, 06:53 #7 Joshua2     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?
2010-02-19, 06:56   #8
Joshua2

Sep 2004

21516 Posts

Quote:
 Originally Posted by wblipp (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.
Where did 40, 30 and 48 come from? I assume the 1+0+0 thing is prime factored?

2010-02-19, 08:04   #9
wblipp

"William"
May 2003
New Haven

2·32·131 Posts

Quote:
 Originally Posted by Joshua2 Where did 40, 30 and 48 come from?
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:
 Originally Posted by Joshua2 I assume the 1+0+0 thing is prime factored?
(40 + 30 + 48) mod 3
=(40 mod 3) + (30 mod 3) + (48 mod 3)
= 1 + 0 + 0
=1

2010-02-19, 15:24   #10
Wacky

Jun 2003
The Texas Hill Country

32×112 Posts

Quote:
 Originally Posted by Joshua2 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?
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

X = 5 A + 3

This transformed the last constraint into

Code:
5 A + 3 == 3 mod 5
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
or, equivalently:

Code:
Find the set of integers "A" such that

2 A == 1 mod 3
and
A == 3 mod 4
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
or equivalently,
Code:
X == 58 mod 60
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"

Last fiddled with by Wacky on 2010-02-19 at 15:52 Reason: Formatting to clarify the presentation

2010-02-19, 21:10   #11
Joshua2

Sep 2004

13×41 Posts

Quote:
 Originally Posted by wblipp 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) = 1 + 0 + 0 =1
I think I understand CRT now. Now I just need to figure out modulo inverses, like what is inverse of 2 mod 5...

 Similar Threads Thread Thread Starter Forum Replies Last Post carpetpool Abstract Algebra & Algebraic Number Theory 1 2017-11-04 16:53 paulunderwood Miscellaneous Math 17 2016-12-31 22:11 paulunderwood Miscellaneous Math 2 2016-12-30 07:34 Dubslow Miscellaneous Math 24 2012-08-24 10:46 flouran Math 4 2008-12-19 17:22

All times are UTC. The time now is 08:19.

Sun Sep 27 08:19:19 UTC 2020 up 17 days, 5:30, 0 users, load averages: 1.81, 1.67, 1.49