Prove that $x^2+3=0 \text{ can be solved in } \mathbb{Z}/7^k\mathbb{Z} \quad \forall k$.

Question

Prove, that $x^2+3=0 \text{ can be solved in } \mathbb{Z}/7^k\mathbb{Z} \quad \forall k$. It's a practice problem in my abstract algebra class, that many people solved but I didn't. The topic of the lecture was about Chinese remainder theorem and groups.

My progress:

• My program shows that there are always exactly 2 solutions $\forall k$, but I didn't find any pattern there.

• I should probably use CRT here, maybe i can get a system of 2 equations with 2 different roots $(mod \quad 7^{k+1})$ from $7^k$?

A hint will be useful

Answer 1

As mentioned in the comments, Hensel's Lemma finishes this problem easily. In fact, it's such an easy solution that I'd probably assume you haven't learned it. Even without access to that lemma, however, it's fairly easy to give an inductive proof:

---

First note that for $k=1$, the solutions are $x \equiv \pm 2 \pmod{7}$.

Now, for an arbitrary $k \geq 1$, suppose we've already shown two distinct solutions $x_1, x_2$ to $x^2 + 3 \equiv 0 \pmod{7^k}$. Then consider $x = x_i + 7^ka$ for an unknown $a$ in the equation modulo $7^{k+1}$: $$(x_i+7^ka)^2 + 3 \equiv x_i^2+3+2ax_i7^k \pmod{7^{k+1}}$$ Using the inductive hypothesis, there is some $b \in \mathbb{Z}$ such that $x_i^2+3 = 7^kb$ so the above congruence gives $$(x_i+7^ka)^2 + 3 \equiv 7^k(b+2ax_i) \pmod{7^{k+1}}$$ In particular, $$(x_i+7^ka)^2 + 3 \equiv 0 \pmod{7^{k+1}} \iff b+2ax_i \equiv 0 \pmod{7}.$$

$b$ and $x_1, x_2$ are fixed by the problem, so we're just checking whether this is solved for any $a$, which will be true as long as $x_i$ is invertible mod $7$. Can you see why this is true?

Answer 2

You can do this by going through the proof of Hensel's lemma for your polynomial. Inductively, if $a_k$ is an integer for which $a_k^2 + 3 \equiv 0 \pmod{7^k}$, then $a_{k+1} = a_k + t_k 7^k$ is an integer for which $a_{k+1}^2 + 3 \equiv 0 \pmod{7^{k+1}}$. Here $t_k$ is any solution to the congruence

$$2a_k t_k \equiv - \frac{a_k^2+3}{7^k}. \pmod{7}$$

Note that by induction, the right hand side of the congruence is indeed an integer, and $t_k$ exists because $2a_k$ is a unit modulo $7$. To check that $a_{k+1}$ does what it is supposed to:

$$a_{k+1}^2 + 3 =(a_k + t_k7^{k})^2 + 3 = a_k^2+3 + 2a_kt_k7^k + t_k^27^{2k} \equiv a_k^2 + 3 + 2a_kt_k7^k \equiv 0 \pmod{7^{k+1}}$$

Answer 3

Geoffrey already gave a nice hint. I'll use a more elementary approach, although not as nice.

Let us consider the multiplicative group $G = (\mathbb{Z}_{7^k})^\times$, which has order $7^k - 7^{k - 1} = 7^{k-1} \cdot 6$. Now, consider the quotient of $G$ by $G^2$, which has order $2$ since $G^2$ has order $\lvert G \rvert / 2$. Note that $-1$ cannot be a square because otherwise $4$ would divide the order of $G$. This shows $-9$ cannot be a square, that is, $3 \cdot (-3)$. Deduce therefore that only one of either $3$ or $-3$ can be a square using the quotient group. Then we must show $3^k \equiv -1$ for some $k$, which shows it cannot be a square because we've seen $-1$ is not a square. It suffices to show that $3$ has even order. Let $d$ be the order of $3$. Then $3^d \equiv 1$ modulo 7 as well, and the order of $3$ there is 6.