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

• Apr 28th 2010, 05:50 AM
moocav
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
• Apr 28th 2010, 08:04 AM
tonio
Quote:

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 $-13485293=667,297\!\!\!\pmod{53\cdot 115\cdot 129=786,255}$ .

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