0
$\begingroup$

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!

$\endgroup$
  • 2
    $\begingroup$ 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$. $\endgroup$ – André Nicolas Dec 14 '13 at 19:21
  • $\begingroup$ Factorization can be helpful when the factors have integer coefficients, but not otherwise. $\endgroup$ – André Nicolas Dec 14 '13 at 19:28
7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Remption Dec 14 '13 at 19:39
  • $\begingroup$ @Remption , I can't understand what you wrote, sorry. $\endgroup$ – DonAntonio Dec 14 '13 at 19:40
  • $\begingroup$ What does quadratic reciprocity mean in the context of the problem. Haven't heard that term before. $\endgroup$ – yiyi Mar 25 '14 at 0:00
  • $\begingroup$ @yiyi, google it. Anyway, the answer doesn't use it. $\endgroup$ – DonAntonio Mar 25 '14 at 0:22
4
$\begingroup$

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

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

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.