Modular arithemtic and CRT

Question

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

Answer 1

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$.

Answer 2

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).