Thread: Find x such that it is congruent to 27mod53, 67mod115 and 109mod129?

Find an integer which is congruent to 27 mod 53, 67 mod 115 and 109 mod 129.
Hint: First find an integer which is congruent to 27 mod 53, 67 mod 115.

Not sure how to go about solving this question. I'm assuming Euclids algorithm is involved to find the gcd but then I don't know what to do

Originally Posted by moocav

Find an integer which is congruent to 27 mod 53, 67 mod 115 and 109 mod 129.
Hint: First find an integer which is congruent to 27 mod 53, 67 mod 115.

Not sure how to go about solving this question. I'm assuming Euclids algorithm is involved to find the gcd but then I don't know what to do

Google "Chinese Remainder Theorem" (CRT) , in particular its proof from which you can understand what to do. This is a very difficult calculating problem (unless

I'm missing some trick to ease it out), and without some kind of programm to evaluate numbers modulo something (and which you can probably find in the

web under ''online calculators modulo" or something like that) , I can't see how to do it without working several hours...good luck!

Tonio


Here! I found this nice site Chinese Remainder Theorem Calculator where it appears one solution is .

As you can see, this is nasty, cruel and mean...unless there's a trick I can't see now.