Finding all solutions to congruence equation

Question

my math professor gave us the following question on a past quiz and I didn't get it right and now I want to know how to do it:

 Find all the solutions to the congruence x^2 is equivalent to 1 mod 437 where
 mod 437=19*23.

I know I have to use the Chinese remainder theorem somewhere, but I'm not quite sure where that comes in...

If someone could give me a step by step walk through on how to do this problem, I would greatly appreciate it! Thanks in advance!

Answer 1

Here's one way of doing it. It does take advantage of the structure of the problem, meaning it won't apply to all problems of this nature. In this problem, the Chinese Remainder Theorem boils down to the statement:

$x \equiv 1 \mod 437 \iff x \equiv 1 \mod 19 \text{ and } x \equiv 1 \mod 23$.

Now, how does this pertain to your question? Well, \begin{align*} x^{2} \equiv 1 \mod 437 &\iff x^{2}-1 \equiv 0 \mod 437 \\ &\iff (x-1)(x+1) \equiv 0 \mod 437 \\ &\iff (x-1)(x+1) \equiv 0 \mod 19 \\ &\hspace{18pt}\text{ and } (x-1)(x+1) \equiv 0 \mod 23 \end{align*} From here, there are four combinations that might work: $x$ is congruent to:

• 1 mod 19 and 1 mod 23
• 1 mod 19 and 22 mod 23
• 18 mod 19 and 1 mod 23
• 18 mod 19 and 22 mod 23

From there, you can find four answers mod 437. Knowing that's the only four answers is a different story, though.