mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Homework Help

Reply
 
Thread Tools
Old 2010-02-17, 20:07   #1
Joshua2
 
Joshua2's Avatar
 
Sep 2004

13×41 Posts
Default 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!
Joshua2 is offline   Reply With Quote
Old 2010-02-17, 20:51   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by Joshua2 View Post
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;
!
??


You answered your own question. Use the CRT.

What else are you looking for? There are plenty of examples.
R.D. Silverman is offline   Reply With Quote
Old 2010-02-17, 20:55   #3
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

2×32×131 Posts
Default

(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.
wblipp is offline   Reply With Quote
Old 2010-02-17, 20:56   #4
Wacky
 
Wacky's Avatar
 
Jun 2003
The Texas Hill Country

21018 Posts
Default

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
Wacky is offline   Reply With Quote
Old 2010-02-18, 07:56   #5
Joshua2
 
Joshua2's Avatar
 
Sep 2004

13×41 Posts
Default

Quote:
Originally Posted by Wacky View Post
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.
Joshua2 is offline   Reply With Quote
Old 2010-02-18, 13:04   #6
Wacky
 
Wacky's Avatar
 
Jun 2003
The Texas Hill Country

21018 Posts
Default

Quote:
Originally Posted by Joshua2 View Post
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?
Wacky is offline   Reply With Quote
Old 2010-02-19, 06:53   #7
Joshua2
 
Joshua2's Avatar
 
Sep 2004

13×41 Posts
Default

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?
Joshua2 is offline   Reply With Quote
Old 2010-02-19, 06:56   #8
Joshua2
 
Joshua2's Avatar
 
Sep 2004

13×41 Posts
Default

Quote:
Originally Posted by wblipp View Post
(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?
Joshua2 is offline   Reply With Quote
Old 2010-02-19, 08:04   #9
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

44668 Posts
Default

Quote:
Originally Posted by Joshua2 View Post
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 View Post
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
wblipp is offline   Reply With Quote
Old 2010-02-19, 15:24   #10
Wacky
 
Wacky's Avatar
 
Jun 2003
The Texas Hill Country

32·112 Posts
Default

Quote:
Originally Posted by Joshua2 View Post
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
We made the substitution

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
Wacky is offline   Reply With Quote
Old 2010-02-19, 21:10   #11
Joshua2
 
Joshua2's Avatar
 
Sep 2004

10258 Posts
Default

Quote:
Originally Posted by wblipp View Post
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...
Joshua2 is offline   Reply With Quote
Reply

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 2017-11-04 16:53
Solving x^2 + x + 1 == 0 (mod mp) paulunderwood Miscellaneous Math 17 2016-12-31 22:11
Solving x^2==1 (mod n) paulunderwood Miscellaneous Math 2 2016-12-30 07:34
New Method for Solving Linear Systems Dubslow Miscellaneous Math 24 2012-08-24 10:46
Solving modular equivalence problems flouran Math 4 2008-12-19 17:22

All times are UTC. The time now is 02:41.

Sat Sep 26 02:41:23 UTC 2020 up 15 days, 23:52, 0 users, load averages: 1.33, 1.32, 1.39

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.