Thread: Chinese Remainder Theorem

For the question,

Find the smallest x which solves the system of congruence equations:

x =+ 3 mod 15
x =+ 6 mod 224, where =+ stands for congruence modulo operation.

I gave an argument oriented solution as follows.

Any multiple of 224 is even.
So, 6+ any multiple of 224 is even.
=> x is even.

Also, any multiple of 15 ends with 5 or 0.
3+any multiple of 15 ends with 8 or 3.

Since X is even, the number should end with 8.
Since X = A number ending with 8,
Also, X = A multiple of 224 + 6
This means the multiple of 224 ends with 2.

Checking the multiples of 224, we get 224, 448, 672.

The smallest one is 672 ==> X is 678.

This solves both the equations as 678 = 224*3 +6
= 45*15 +3

My friend argued about a general solution for the same problem using Chinese Remainder Theorem. I browsed results for the same in various sites.
I find only a general solution found in most cases.

Can anyone describe how to get the particular solution for this problem through Chinese Remainder Theorem?

Also, please mention if there are any mistakes in my argument-oriented solution.

yes you can....

so we have

3 mod 15
6 mod 224

gcd(224,15)=1 so we use chinese thm.

first thing we need is integers a and b s.t...

a15+b224=1

and after we find a and b using euclid's algorithm we compute

6a15+3b224 (mod 15.224=3360)

euclid's algorithm gives a=15 and b=-1

so 6(15)15+3(-1)224=678 mod 3360

and adding and subtracting 3360 would give you many solutions.


you can also use this method to solve many problems which your method would be increasingly difficult to use for example....

Find a number which is 3 mod 7, 2 mod 5 and 1 mod 2.

7,5 and 2 are coprime so use chinese thm...

first concentrate on 3 mod 7 and 2 mod 5

find a,b so that a7+b5=1

a=-2 and b=3 using euclid

compute 2a7+3b5 (mod 7.5=35)=2(-2)7+3(3)5=17 mod 35


now do the same with 17 mod 35 and 1 mod 2

i need to compute 1a35+17b2 where a35+b2=1

a=1 and b=-17

so 1a35+17b2=17 mod 70=87mod70


Note: the reason why we need the gcd to be 1 is because the chinese remainder theorem is based on this.


but you have a nice little argument there, nice one.

Here's a similar argument:

x= 6 mod 224 so x= 224k+ 6 for some integer k. But 224= 14 mod 15 so that is the same as x= 14k+ 6 mod 15. We have x= 14k+ 6= 3 mod 15 or 14k= -3 mod 15 so 14k= 15j- 3 for some integer j. That is, 15j- 14k= 3. It is obvious that 15- 14= 1 (shortcutting the Euclidean division algorithm!) so 15(3)- 14(3)= 3. k= j= 3 is a solution. Taking k= 3, x= 224(3)+ 6= 678.

But if you can come up with a valid argument of your own, that's always best.

@Krahl
Thanks for your descriptive reply for the question; I get the solution part right till the general solution; You had mentioned that adding and subtracting 3360 would yield other solutions; It is this part where I do mistakes some times.

Can you please throw some more light on one or two of the particular solutions?



MAX,

@HallsofIvy

That's another interesting aliter for the same problem; Good one

I was just thinking it might actually help you to see the actual proof of the theorem so you can see why these solution methods actually work. I am not sure if you are familiar with rings and ideals and stuff, so I will leave it in terms of the integers, but if you are interested, the same proof idea works in general.

You assume that (m,n)=1 (this is enough to show in a ring (m)+(n)=R).
Then you have the following isomorphism:


Here is the isomorphism:
(mod m), (mod n)).
It is a homomorphism:
(mod m), (mod n)) (mod m), (mod n)) (mod m), (mod n))= .

It is pretty clear that

So it remains to show that it is surjective, and this is the key part of the argument for what you are looking for.

Let (mod m), (mod n)) be an arbitrary element of

This is basically saying we need some integer that will satisfy
(mod m) and
(mod n).

So this is the trick. Because we know (m, n) by the euclidean algorithm, there exists such that .

Just a side note: In the more general setting you say that the ring contains a unit and since we have (m)+(n)=R, there exists and such that . Actually the ring need not even be a PID, it is true for any ideals that are comaximal in a commutative ring.

So back to the surjectivity. We want to sort of cross multiply here and take the value and see that it maps where we want it.

(mod m), (mod n)) (mod m), (mod n))= (mod m), (mod n))= (mod m), (mod n))= (mod m), (mod n)).

So this proves the isomorphism. This shows you (mod mn) is the number you want to pick to solve the system of equations above.

The fact that the kernel is just tells you that you can actually just add kmn for any integer k to your solution and you will get all the solutions to this system of equations.

Hope this was helpful.

Originally Posted by MAX09

@Krahl
Thanks for your descriptive reply for the question; I get the solution part right till the general solution; You had mentioned that adding and subtracting 3360 would yield other solutions; It is this part where I do mistakes some times.

Can you please throw some more light on one or two of the particular solutions?



MAX,

Hi max

not sure what part of the solution you're asking for but i'll try writing a few things on the solutions.

well you agree that 678 is a solution right?

Now the useful thing about using the chinese rem thm is that you end up not just with the answer 678 but also mod 3360.

This mean that any number which is modulo 3360 would satisfy your equations,

for example if we add and subtract 3360 we get the following alternative solutions;

........, -2682,678,4038,7398.......,

Now this means that all these numbers are 678 modulo 3360
i.e. have remainder 678 when divided by 3360.

so 4038=3360+678, 7398=3360*2+678 etc...

And the theorem claims that all these solutions also satisfy, so let's check them;


7398=15*493+3 so it is 3 mod 15

7398=224*33+6 so it is 6 mod 224

That is why the question asks for the smallest positive solution.

I did the same with the other example and got the solutions 17 mod 70 and 87 mod 70.

Also notice this step i did;

6a15+3b224


its 6 mod 224 that is why 6 is next to 15. since 224 = 0 mod 224 so that you are left with 6a15 + 0 mod224

and so a*15 must give me 1 mod 224 so that
6a15+0 mod 224=6 mod 224

and same with mod 15.

any problems dont hesitate to post

@Gamma

That wasn't exactly the procedure I was looking for. Anyways, thanks for the effort.. It helped understanding the relation the CRT had with isomorphisms. Thanks a bunch !!!

Yes, your posted help me understand the procedure completely I had to get my basics on the Extended Euclidean Algorithm right. The following url helped me.

http://marauder.millersville.edu/~bikenaga/absalg/euc/euclidex.html

Thanks again, Krahl!!

Max