Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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 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 at 9:59

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.