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

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!

• The factorization $(x-\sqrt{5})(x+\sqrt{5})$ is (at this level) a not good move. To see that $x^2\equiv 5\pmod{7}$ has no solution, it is easiest to "try everything." It is enough to try $x=0,1,2,3$. Dec 14, 2013 at 19:21
• Factorization can be helpful when the factors have integer coefficients, but not otherwise. Dec 14, 2013 at 19:28

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$$

• To ensure I understand this correctly, you're basically using the rule that x≡a (mod b) ⟹ x^k ≡ a^k (mod b) to prove there's no solution? Dec 14, 2013 at 19:39
• @Remption , I can't understand what you wrote, sorry. Dec 14, 2013 at 19:40
• What does quadratic reciprocity mean in the context of the problem. Haven't heard that term before.
– yiyi
Mar 25, 2014 at 0:00
• @yiyi, google it. Anyway, the answer doesn't use it. Mar 25, 2014 at 0:22

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).

• Just to make sure I understand the "Cube", it means that you can cube all the integers in the problem? How is that possible?
– yiyi
Mar 25, 2014 at 0:01
• @yiyi See the edited answer. Mar 25, 2014 at 0:09
• You replied so fast, The force is strong with you.
– yiyi
Mar 25, 2014 at 0:13

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$).

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.