Finding all solutions for congruences

Question

Decide which of the following congruences are solvable, and if so, find all solutions:

a) $x^2 \equiv c \bmod 363$, where $c= 1,5,31$

b) $x^2 \equiv 54 \bmod 125$

Now, I know how to find which of those are solveable, but I have no idea how to find the solutions.

(For example b) is solvable).

Any ideas?

Answer 1

Perhaps these general ideas can help you:

Suppose that we want to solve $x^k \equiv c \bmod p_1^{\alpha_1}p_2^{\alpha_2}\dots p_n^{\alpha_n}$

It suffices to find the solutions $\bmod p^a$ for each prime power and then combine them using the chinese remainder theorem.

So how can we solve $x^k\equiv c \bmod p^a$?

One way is to do it inductively over $a$.

First find all the solutions to $x^k \equiv p^{a-1}$, so when we check for the solutions to $x^k\equiv p^{a-1}$ we only have to check congruences which also solved the previous equation.