Thread: solving modular constraints View Single Post
2010-02-19, 15:24   #10
Wacky

Jun 2003
The Texas Hill Country

2·541 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