Question

Find all solutions of the congruence$x^2\equiv 29(mod35)$.

Short answer

The solutions are 8, 13, 22 or 27(mod 35).

Step-by-step solution

Step: 1

Since 35= 5.7

$$\begin{gathered} \begin{array}{r}{x}^2\equiv 4(mod5)\\ x^2\equiv 1(mod7)\end{array} \\ \begin{array}{r}x\equiv \mathrm{2.7.3}+\mathrm{1.5.3}(mod35)\\ x=57(mod35)\\ x\equiv 22(mod35)\end{array} \end{gathered}$$

Step: 2

$\begin{array}{r}x\equiv \mathrm{3.7.3}+\mathrm{1.5.3}(mod35)\\ x=78(mod35)\\ x\equiv 8(mod35)\\ \\ x\equiv \mathrm{3.7.3}+\mathrm{6.5.3}(mod35)\\ x=153(mod35)\\ x\equiv 13(mod35)\end{array}$

Step: 3

So, all the solutions are 8, 13, 22 or 27(mod 35).