Question

Find all solutions of the congruence$x^2\equiv 16(mod105)$.

Short answer

The solutions of the congruence$x^2\equiv 16(mod105)\text{is}x=105k\pm 11$for some integer k.

Step-by-step solution

Step: 1

$\begin{array}{r}{x}^2\equiv 16(mod105)\\ \\ x^2=1mod3\\ \\ x^2\equiv 16mod5\\ \\ x^2\equiv 1mod5\\ \\ x^2=16mod7\\ \\ x^2\equiv 2mod7\end{array}$

Step: 2

$\begin{array}{r}{x}^2\equiv \left[35\right(2)+21(1)+30(1\left)\right]mod105\\ x^2\equiv 121(mod105)\\ x^2-121\equiv 0(mod105)\\ 105\mid x^2-121\\ 105\mid (x+11)(x-11)\end{array}$

Step: 3

For some integer k:

$\begin{array}{r}x=105k\pm 11\\ x=105\pm 11\end{array}$