solving modular constraints

[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'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!

[R.D. Silverman]

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.

<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.

[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. 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.

[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

[Joshua2]

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.

[Wacky]

Originally Posted by Joshua2

Is this the CRT as well?

Why don't you tell us? Is it, or is it not? Why?

Its seems we can't continue with 2A = 1 + 3A and A = 3 + 4A? I think I did that wrong.

A correct observation.

How about A = 3 + 4B and 2A = 1 + 3 B

That's the spirit

with two equations and two unknowns?

Is that what we did before?

[Joshua2]

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]

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?

[wblipp]

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

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

[Wacky]

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:

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

5 A + 3 == 3 mod 5

which is true for all integers A

That left us with the equivalent problem:

Find the set of integers "A" such that

5 A + 3 == 1 mod 3
and
5 A + 3 == 2 mod 4

or, equivalently:

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

X = 60 C + 58

or equivalently,

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"

[Joshua2]

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...