# Chinese Number Theorem w/ extended Euclidean Algorithm

I am given the following:

153 = x^3 mod 155
196 = x^3 mod 203
27 = x^3 mod 117


My first thought was that I could turn this into an equivalence and say

153 ≡ x^3 mod 155 so then x^3 ≡ 153 mod 155
196 ≡ x^3 mod 203 so then x^3 ≡ 196 mod 203
27 ≡ x^3 mod 117 so then x^3 ≡ 27 mod 117


To me the above looks like a perfect example of when to use the Extended Euclidean algorithm with the Chinese Remainder Theorem. I used a website to calculate the Extended Euclidean Algorithm found here: http://www.numbertheory.org/php/euclid.html#euclid

So my results were:

gcd(153, 203*117) = (621)*(153) + (-4)*(23751)
gcd(196, 155*117) = (-5459)*(196) + (59)*(18135)
gcd(27, 155*203) = (9323)*(27) + (-8)*(31465)


Based on my understanding of the Chinese Remainder Theorem, x^3 should equal:

(-4)*(23751) + (59)*(18135) + (-8)*(31465)  = 723241


However, given x^3 = 723241,

723241 mod 155 = 11
723241 mod 203 = 155
723241 mod 117 = 64


DOES NOT SATISFY

153 = x^3 mod 155
196 = x^3 mod 203
27 = x^3 mod 117


Is there an issue with my logic/reasoning? Is the calculator I am using incorrect? Or Am I looking at this the wrong way?

-
ASIDE: it's usually better to solve for $x$ for three small moduli, then use the CRT to get the answer for one large modulus than it is to use the CRT first then solve for $x$. –  Hurkyl Feb 17 '14 at 9:50
I am not sure what I would gain from that in this case since the only even power of 3 is 27, I feel like that would further complicate my solution. –  BoZa Feb 17 '14 at 9:59