Solve $x^2 \equiv 29\pmod {35}$ What are the solutions of the congruence $x^2 \equiv 29\pmod {35}$. Use congruence modulo $5$ and modulo $7$.
 A: $$
x^2 \equiv 29 \equiv 4 \mod 5\\
x^2 \equiv 29 \equiv 1 \mod 7
$$
Solve each of the two equations for $x$, you'll get two solutions each. Then, use Chinese Remainder Theorem to find values of $x$ mod 35.
A: Solving modulo the primes $\,5,7,\,$ then combining solutions by CRT (Chinese Remainder),
$\rm\quad x^2\equiv 4\ \ (mod\ 5)\:\Rightarrow\: 5\mid(x-2)(x+2)\:\Rightarrow\:5\mid x\!-\!2\ \ or\ \ 5\mid x\!+\!2\:\Rightarrow\:x\equiv \color{#0A0}2,\color{blue}{-2}\ \ (mod\ 5)$
$\rm\quad x^2\equiv 1\ \ (mod\ 7)\:\Rightarrow\: 7\mid(x-1)(x+1)\:\Rightarrow\:7\mid x\!-\!1\ \ or\ \ 7\mid x\!+\!1\:\Rightarrow\:x\equiv \color{#C00}1,-1\ \ (mod\ 7)$
Now combine solutions by CRT. If $\rm\:x\equiv a\pmod 5,\ \ x\equiv b\pmod 7\:$ then $\rm\: x = b + 7n,\:$ so $\rm\: mod\ 5\!:\ a \equiv x\equiv  b + 7n\equiv b+2n\!\iff\! \color{#90f}{2n\equiv a-b}.$
Case $\rm1\!:\,\ a\equiv \color{#0A0}2,\ b\equiv \color{#C00}1,\,\ $ hence $\rm\,\ mod\ 5\!:\ \color{#90f}{2n\equiv a-b} \equiv 1\equiv 6\:\Rightarrow\:n\equiv 3,\ $ so $\rm\ n = 3+5k,\ $ so $\rm\ x = b+7n = 1+7(3+5k) = 22+35k.\:$
Case $\rm2\!:\,\ a\equiv \color{#0A0}2,\ b\equiv -1,\, $ hence $\rm\, mod\ 5\!:\ \color{#90f}{2n\equiv a-b} \equiv 3\equiv 8\:\Rightarrow\:n\equiv 4,\ $ so $\rm\ n = 4+5k,\ $ so $\rm\ x = b+7n = -1+7(4+5k) = 27+35k.\:$
The other $\,2\,$ cases $\rm\: (a,b)\equiv (\color{blue}{-2},\color{#C00}1),\ (\color{blue}{-2},-1)\:$ are solved similarly.
