Solve $x^2\equiv 5 \pmod {35}$

Question

I'm studying for an exam and came across this problem:

Solve $x^2 \equiv5\pmod {35}$

This is what I ended up with:

$x^2 \equiv 0\pmod 5$

$x^2 \equiv 5\pmod 7$

$5\mid x^2 \implies 5\mid x\cdot x\implies 5\mid x ⇒ x \equiv 0\pmod 5$

$7\mid x^2 - 5 \implies 7\mid(x -\sqrt{5})(x +\sqrt{5})\implies$ ???

I assume this means there is no solution to the congruence, but am not certain. Is there any way you could use the Chinese Remainder Theorem to solve this? What if it was $x^2≡ 3$ (mod $35$) instead? I assume there is the same exact issue. Thanks!

Answer 1

Hint:

Working all through the following modulo $\;7\;$ (without using quadratic reciprocity) :

$$0^2=0\;,\;1^2=1\;,\;2^2=4\;,\;3^2=2\;,\;4^2=2\;,\;5^2=4\;,\;6^2=1\;,\;$$ but

$$x^2=5\pmod {35}\implies x^2=5\pmod 7\;\ldots\ldots$$

Answer 2

Hint $\rm\ \ mod\ 7\!:\ x^2\equiv 5\equiv -2\ \overset{cube}\Rightarrow\ x^6 \equiv -1,\ $ contra little Fermat. Alternatively, list all squares.

Answering a comment question: generally $\,a\equiv b\,\Rightarrow\,a^3\equiv b^3,\,$ by the Congruence Power Rule below. Thus, in particular, this implies $\,\ x^2\equiv -2\,\Rightarrow\,x^6\equiv(-2)^3\equiv -1\pmod 7.$

---

Congruence Sum Rule $\rm\qquad\quad A\equiv a,\quad B\equiv b\ \Rightarrow\ \color{#c0f}{A+B\,\equiv\, a+b}\ \ \ (mod\ m)$

Proof $\rm\ \ m\: |\: A\!-\!a,\ B\!-\!b\ \Rightarrow\ m\ |\ (A\!-\!a) + (B\!-\!b)\ =\ \color{#c0f}{A+B - (a+b)} $

Congruence Product Rule $\rm\quad\ A\equiv a,\ \ and \ \ B\equiv b\ \Rightarrow\ \color{blue}{AB\equiv ab}\ \ \ (mod\ m)$

Proof $\rm\ \ m\: |\: A\!-\!a,\ B\!-\!b\ \Rightarrow\ m\ |\ (A\!-\!a)\ B + a\ (B\!-\!b)\ =\ \color{blue}{AB - ab} $

Congruence Power Rule $\rm\qquad \color{}{A\equiv a}\ \Rightarrow\ \color{#c00}{A^n\equiv a^n}\ \ (mod\ m)$

Proof $\ $ It is true for $\rm\,n=1\,$ and $\rm\,A\equiv a,\ A^n\equiv a^n \Rightarrow\, \color{#c00}{A^{n+1}\equiv a^{n+1}},\,$ by the Product Rule, so the result follows by induction on $\,n.$

Polynomial Congruence Rule $\ $ If $\,f(x)\,$ is polynomial with integer coefficients then $\ A\equiv a\ \Rightarrow\ f(A)\equiv f(a)\,\pmod m.$

Proof $\ $ By induction on $\, n = $ degree $f.\,$ Clear if $\, n = 0.\,$ Else $\,f(x) = f(0) + x\,g(x)\,$ for $\,g(x)\,$ a polynomial with integer coefficients of degree $< n.\,$ By induction $\,g(A)\equiv g(a)\,$ so $\, A g(A)\equiv a g(a)\,$ by the Product Rule. Hence $\,f(A) = f(0)+Ag(A)\equiv f(0)+ag(a) = f(a)\,$ by the Sum Rule.

Beware $ $ that such rules need not hold true for other operations, e.g. the exponential analog of above $\rm A^B\equiv a^b$ is not generally true (unless $\rm B = b,\,$ so it reduces to the Power Rule, so follows by inductively applying $\,\rm b\,$ times the Product Rule).

Answer 3

If $x^2\equiv 5$ (mod $35$), then since $5$ and $7$ divide $35$, it is also true that $x^2\equiv 5$ (mod $5$) and $x^2\equiv 5$ (mod $7$), ie. $x^2\equiv 0$ (mod $5$) and $x^2\equiv 5$ (mod $7$). The only numbers $<35$ that square to $0$ (mod $5$) are $0,5,10,15,20,25,30$ and none square to $5$ (mod $7$).

Answer 4

The solution of $x^2 \equiv 5 (\mod 35)$ is also a solution of $x^2 \equiv 5 (\mod 7)$. But by Euler's criterion, we have $5^{\frac{7-1}{2}} \equiv-1 (\mod 7)$, which tells us that the congruence $x^2 \equiv 5 (\mod 7)$ has no solution. Hence, the congruence $x^2 \equiv 5 (\mod 35)$ also has no solution.