How to find the solutions of a^2 = [29] mod 35? How to find the solutions of: $$a^2 = [29]_{35}$$ ?
(Brutal) Attempt:
Since $Z_{35}$ contains only 35 elements, one could just brute force the calculation of $a^2$ for every element a $\in Z_{35}$ that GCD(a,35). When you find a number that verifies the equation, automatically you find another solution which is the inverse of that solution $\in Z_{35}$.
Do you know any non brutal way?
NOTE: it doesn't have to require the quadratic congruence solving (I have only studied linear congruences)
 A: Note that $35 = 7 \times 5$, so solving the congruence relation is the same as solving the follwoing system:
$$a^2 \equiv 29 \equiv 4 \pmod 5 \iff (a-2)(a+2) \equiv 0 \pmod 5$$
$$a^2 \equiv 29 \equiv 1 \pmod 7 \iff (a-1)(a+1) \equiv 0 \pmod 7$$
Because we have prime modulii then exactly one of the number is divisible by $5,7$. Check every possible combination (there are 4 combinations in this case) and then just simply apply Chinese Remainder Theorem.

UPDATE: Here's an example for finding one solution. As I've said exactly one of the factors is divisible by one. One combination is:
$$a - 2 \equiv 0 \pmod 5 \iff a \equiv 2 \pmod 5$$
$$a - 1 \equiv 0 \pmod 7 \iff a \equiv 1 \pmod 7$$
Now just apply the Chinese Remadiner Theorem to "glue" the two relations (I assume you know how to do that) and you'll get that $a \equiv 22 \pmod {35}$ is one solution. Now you have three more combinations to go.
If you don't understand how to get $(a-2)(a+2) \equiv 0 \pmod 5$ from $a^2 \equiv 4 \pmod 5$, then it's easier just to take square root and you'll get $a \equiv \pm 2 \pmod 5$. We can certainly do this because $4$ is a square and $5$ is a prime number. Actually this works due to the factorization I've posted earlier.
