MHB Why do these conditions have to be satisfied?

[evinda]

Hello! (Smile)

When we have a congruence $x^2 \equiv a \pmod {p^n}, n=1,2,3, \dots$ , and we know a solution $\pmod {p^n}$, then we also know a solution $\pmod {p^l}, l<n$.

For example, we know that for $n=3$, the congruence $\displaystyle{ x^2 \equiv 2 \pmod { 7^3}}$ has the solution

$$x_0 \equiv 108 \pmod {7^3} \equiv 108 \pmod {343}$$

Obviously, $x_0' \equiv 108 \pmod {49}$ is a solution of $x^2 \equiv 2 \pmod {7^2}$.

Also, $\displaystyle{ x_0'' \equiv 3 \pmod 7}$ is a solution of $x^2 \equiv 2 \pmod 7$.We want to do the reverse.

We know a solution $x_0 \pmod p$ of $x^2 \equiv a \pmod p$, and we want to find a solution $\pmod {p^2}$.
Applying this at the example $x^2 \equiv 2 \pmod 7$, we have $x_0=a_0=3$.

We are looking for a $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}$$I haven't understood why, when we have a solution $\pmod p$, and we are looking for a solution $\pmod {p^2}$, we are looking for a $x_1$, such that:

$$x_1^2 \equiv 2 \pmod {7^2} \text{ such that } x_1 \equiv x_0 \pmod{7}$$

Could you explain it to me? (Sweating)

 

[mathbalarka]

I presume you are quoting a part of some book you have? You should snapshot the relevant page to give the readers a better idea of what is going on there (of course, only if you have a soft copy of it). From what I can exert from there, the relevant paragraph is merely a step of the whole calculations, which you have apparently omitted.

I haven't understood why, when we have a solution (mod p), and we are looking for a solution (mod p^2), we are looking for a x_1, such that:

Given a solution $x = x_0$ to $x^2 = a$ modulo some prime $p$, if you are looking for solutions of $x^2 = a$ modulo $p^2$, the first step would be to "sieve out" the natural numbers to look only for solutions $a \pmod{p}$ as

$$x^2 = a \pmod{p^2} \Longrightarrow x = a \pmod{p}$$

The converse doesn't hold, however! There is a lot of examples of numbers which differ modulo 2 and 4, for example. That is why I believe there is more to it than what you have posted.