# Modular arithemtic and CRT

I'm trying to solve the following congruence:

$71x-1 \equiv 0 \pmod{59367}$

Given that $59367=771 \times 77$, I have previously solved that:

$71x \equiv 1 \pmod{771}$ such that $x=-76$

$71x \equiv 1 \pmod{77}$ such that $x=-13$

I'm trying to use the Chinese Remainder Theorem, but seem to be getting the wrong answer, if anyone can work this out so I can try and understand where it is that I'm going wrong?

Thank you

• If you could tell us where you are going wrong while using Chinese remainder theorem,we could help you better.Besides,the steps that you took are correct,but quite unnecessary in resolving the problem at hand. – rah4927 Apr 20 '14 at 15:40

## 2 Answers

No need to use the CRT for 1 equation, just find the modular inverse of $71$ in the equation $71x ≡ 1 \pmod{59367}$, that will give you the value of $x$.

• Yes you certainly correct. I was over-complicating it!! Thank you, I got x=48497 – sarahusher Apr 20 '14 at 12:52
• Would I be able to use the CRT (even though it's more complicated) ? Merely for sake of practice? – sarahusher Apr 20 '14 at 13:00
• No, you may not.There is no logical way to decompose an equation into two to like you did because x mod (a*b) may not equal to (x mod a) and (x mod b). and you can mark the answer correct. – Tamim Addari Apr 20 '14 at 13:16
• It is true.Consider what those statements mean in the form of standard equation.$59637k+1=71x$.This is equivalent to $(771)(77k)+1=71x$ and $(77)(771k)+1=71x$. – rah4927 Apr 20 '14 at 13:22
• owh, that's correct. then perhaps crt can used if the numbers are co-prime. – Tamim Addari Apr 20 '14 at 13:32

Using the modular inverse is the easiest way to the solution, but it can be found using the CRT. 59367 = 3*7*11*257 = 3*77*257. 71x = 1(mod 3), 71x = 1(mod 77), and 71x = 1(mod 257). Solving these equations for x, you get

X = 2(mod 3)

X = 64(mod 77)

X = 181(mod 257)

Solving the first two equations simultaneously, you get x = 218(mod 231).

Solving this result with the third equation, simultaneously you get the final answer

x = 48497(mod 59367).