Solutions mod $p^n$: Finding x$_1 \pmod {7^2}$

[evinda]

Hi! (Blush)

We have a solution $x_0 \pmod 7$ of $x^2 \equiv a \pmod 7$.
To find a solution $\pmod {7^2}$, we are looking for $x_1 \in \mathbb{Z}$ such that $$x_1^2 \equiv 2 \pmod {7^2} \text{ such that } x_1 \equiv x_0\pmod 7$$

We write $x_1=x_0+7a_1$ and we replace it.

We have $x_1^2-2=(3+7a_1)^2-2=7+6 \cdot 7 a_1+a_1^2 7^2 \equiv 7(1+6a_1) \pmod {7^2}$

Therefore: $x_1^2-2 \equiv 0 \pmod{7^2} \Leftrightarrow 1+6a_1 \equiv 0 \pmod 7 \Leftrightarrow a_1 \equiv 1 \pmod 7 \Leftrightarrow x_1 \equiv 10 \pmod{7^2}$

We continue by using induction.

We suppose that we have a solution $\displaystyle{x_n=\sum_{i=0}^{n}a_i7^i}$ of $x_n^2-2 \equiv \pmod {7^{n+1}}$

Then, we are looking for $x_{n+1}$ such that $$x_{n+1}^2-2 \equiv 0 \pmod {7^{n+2}} \text{ and } x_{n+1} \equiv x_n \pmod {7^{n+1}}$$

We set $x_{n+1}=x_n+a_{n+1}7^{n+1}$ and we have:

$$0 \equiv x_{n+1}^2-2 =(x_n+a_{n+1}7^{n+1})^2-2 = x_n^2-2+2x_n a_{n+1} 7^{n+1}+a_{n+1}^2 7^{2n+2} \\ \equiv (x_n^2-2)+2 x_n a_{n+1}7^{n+1} \pmod {7^{n+2}} \equiv 7^{n+1} b_{n+1}+2x_na_{n+1}7^{n+1} \pmod {7^{n+2}}$$

Do we get the term $b_{n+1}$ from : $$x_n^2-2 \equiv 0 \pmod {7^{n+1}} \Rightarrow x_n^2-2 = 7^{n+1}b_{n+1}$$ ?
$$x_{n+1}^2-2 \equiv 7^{n+1}(b_{n+1}+2x_na_{n+1}) \pmod {7^{n+2}}$$
$$x_{n+1}^2-2 \equiv 0 \pmod {7^{n+2}} \Leftrightarrow 2x_na_{n+1}+b_{n+1} \equiv 0\pmod 7$$

Since $x_n \equiv x_0 \pmod 7$, $$x_{n+1}^2-2=0 \Leftrightarrow 2a_{n+1}x_0+b_{n+1} \equiv 0 \pmod 7 \Leftrightarrow 6a_{n+1}=-b_{n+1} \pmod 7 \Leftrightarrow a_{n+1}\equiv b_{n+1} \pmod 7$$

This congruence has an unambiguous solution $\pmod 7$, $a_{n+1} \in \{0,1,2, \dots, 6 \}$. $(*)$

$$\Rightarrow x_{n+1} \sum_{i=0}^{n+1} a_i 7^i$$

Could you explain me how we conclude that the congruence has an unambiguous solution $\pmod 7$, when $a_{n+1} \equiv b_{n+1} \pmod 7$ ?

And also, we had set that $\displaystyle{x_{n+1}=x_n+a_{n+1}7^{n+1}}$, where $\displaystyle{x_n=\sum_{i=0}^{n}a_i7^i}$. Can we write $\displaystyle{x_{n+1}=\sum_{i=0}^{n+1}a_i7^i}$ because of $(*)$ ? Or is there an other reason?

 

[jvicens]

Thank you for your question. To answer your first question, we can conclude that the congruence has an unambiguous solution $\pmod 7$ because the coefficients $a_{n+1}$ and $b_{n+1}$ are both integers and the modulus $7$ is a prime number. This means that $a_{n+1}$ and $b_{n+1}$ have a unique remainder when divided by $7$, and therefore there is only one possible solution for $a_{n+1}$ that satisfies the congruence.

As for your second question, yes, we can write $x_{n+1}=\sum_{i=0}^{n+1}a_i7^i$ because of $(*)$. This is because we are using the same method as in the previous steps, where we set $x_{n+1}=x_n+a_{n+1}7^{n+1}$ and then find the value of $a_{n+1}$ that satisfies the congruence. This value will then be added to the previous terms in the sum, resulting in a new sum with one more term. This process can be repeated for any number of terms, allowing us to write $x_{n+1}$ in terms of $x_n$ and the coefficients $a_i$. I hope this helps to clarify your doubts. Let me know if you have any further questions.