Find the least non-negative residue $x$ modulo $n$ in the following cases:
(a) $x^2 ≡ 25 \pmod 3$
(b) $x^2 ≡ 100 \pmod {11}$
Also determine the general solution in each case.
(a) We have
$$\begin{align} x^2 & \equiv 25 \pmod 3 \\ \\ x^2 - 25 & \equiv 0 \pmod 3 \\ \\ (x-5) (x+5) & \equiv 0 \pmod 3 \end{align}$$
Proposition 3.14(b) gives us $(x-5) \equiv 0 \pmod 3$ or $(x+5) \equiv 0 \pmod 3$. Let's consider each case in turn.
Case 1: $(x-5) \equiv 0 \pmod 3$ gives us $x = 5 +3t$ for some integer $t$.
Case 3: $(x+5) \equiv 0 \pmod 3$ is $x \equiv 1 \pmod 3$, which gives us $x = 1 +3t$ for some integer $t$.
The least non-negative residue is 1 from the second case with $t=0$.
The general solution is $x = 3t + 3 \pm 2$.
(b) This time we use $10^2 \equiv (-1)^2 \pmod 11$,
$$\begin{align} x^2 & \equiv 100 \pmod {11} \\ \\ x^2 & \equiv 10^2 \pmod {11} \\ \\ & \equiv 1\pmod {11} \\ \\ x^2 -1 & \equiv 0 \pmod {11} \\ \\. (x+1) \times (x-1) & \equiv 0 \pmod {11}\end{align}$$
Proposition 3.14(b) gives us $(x-1) \equiv 0 \pmod {11}$ or $(x+1) \equiv 0 \pmod{11}$. Let's consider each case in turn.
Case 1: $(x-1) \equiv 0 \pmod {11}$ gives us $x = 1 + 11t$ for some integer $t$.
Case 1: $(x+1) \equiv 0 \pmod {11}$ is $x \equiv 10 \pmod {11}$, which gives us $x = 10 + 11t$ for some integer $t$.
The least non-negative residue is 1 from the first case with $t=0$.
The general solution is $x = 11t + \frac{11}{2} \pm \frac{9}{2}$.