Square root mod $p^2q$ of a negative residue

Question

Problem: I'm asked to calculate the square roots of $\,-6\,\left(\mbox{mod}\;245\right)$.

---

First step

Since $\,245=7^2\cdot5$, I define $\,p=7\,$ and $\,q=5$ to apply the CRT and reduce the problem to \begin{align} x^2\equiv&-6\;\;\left(\mbox{mod}\;p^2\right)\\ x^2\equiv&-6\;\;\left(\mbox{mod}\;q\right) \end{align}

Second step

Let $\,a\in\mathbb{Z}^+$ be a quadratic residue $\left(\mbox{mod}\;p\right)$. I proved that given a solution of $\,y^2\equiv a\,\left(\mbox{mod}\;p\right)$, I can find $\,r\in\mathbb{Z}\,$ such that $$\frac{y^2-a}{p}+2yr\equiv0\;\;\left(\mbox{mod}\;p\right)$$ to obtain a solution for $\,x^2\equiv a\,\left(\mbox{mod}\;p^2\right)$ by typing $\,x = y + rp$.

Question

It may be stupid to ask this, but how do I proceed? I'm stuck cause $\,-6\notin\mathbb{Z}^+$ and I don't know how to get $\,a$.

Answer 1

First solve mod $5$ . . . \begin{align*} &x^2\equiv -6\;(\text{mod}\;5) \qquad\qquad\;\; \\[4pt] \iff\;&x^2\equiv 4\;(\text{mod}\;5)\\[4pt] \iff\;&x\equiv \pm 2\;(\text{mod}\;5)\\[4pt] \end{align*} Next solve mod $7$ . . . \begin{align*} &x^2\equiv -6\;(\text{mod}\;7) \qquad\qquad\;\; \\[4pt] \iff\;&x^2\equiv 1\;(\text{mod}\;7)\\[4pt] \iff\;&x\equiv \pm 1\;(\text{mod}\;7)\\[4pt] \end{align*} Next solve mod $49$ . . .

For the case $x\equiv 1\;(\text{mod}\;7)$, write $x=1+7s$, for some integer $s$. \begin{align*} \text{Then}\;\;&x^2\equiv -6\;(\text{mod}\;49)\\[4pt] \iff\;&(1+7s)^2\equiv -6\;(\text{mod}\;49)\\[4pt] \iff\;&1+14s\equiv -6\;(\text{mod}\;49)\\[4pt] \iff\;&14s\equiv -7\;(\text{mod}\;49)\\[4pt] \iff\;&2s\equiv -1\;(\text{mod}\;7)\\[4pt] \iff\;&s\equiv 3\;(\text{mod}\;7)\\[4pt] \iff\;&s=3+7t\;\text{for some integer}\;t\\[4pt] \iff\;&x=1+7(3+7t)\\[4pt] \iff\;&x\equiv 22\;(\text{mod}\;49)\\[4pt] \end{align*} For the case $x\equiv -1\;(\text{mod}\;7)$, by analogous steps, we get $x\equiv -22\;(\text{mod}\;49)$.

Thus $x^2\equiv -6 \;(\text{mod}\;245)\;$if and only if $$ \begin{cases} x\equiv \pm 2\;(\text{mod}\;5)\\[4pt] x\equiv \pm 22\;(\text{mod}\;49)\\ \end{cases} \qquad\qquad\qquad $$ To finish, apply the Chinese Remainder Theorem to get $4$ solutions, mod $245$.

Answer 2

Numerically:

? for(x=0,244,if(Mod(x^2,245)==-6,print1(x", ")))
22, 27, 218, 223,

Theorycally:

? print(factorint(245))
[5, 1; 7, 2]
?
? polrootsmod(x^2+6,5)
%4 = [Mod(2, 5), Mod(3, 5)]~
?
? polrootsmod(x^2+6,7)
%5 = [Mod(1, 7), Mod(6, 7)]~
?
? polhensellift(x^2+6,[x+1,x+6],7,2)
%6 = [x + 22, x + 27]
?
? chinese(Mod(2,5),Mod(22,49))
%7 = Mod(22, 245)
?
? chinese(Mod(2,5),Mod(27,49))
%8 = Mod(27, 245)
?
? chinese(Mod(3,5),Mod(22,49))
%9 = Mod(218, 245)
?
? chinese(Mod(3,5),Mod(27,49))
%10 = Mod(223, 245)