Quadratic residue and the p-adic numbers
Show that the equation \( x^2 = 2 \) has a solution in \( \mathbb{Z}_7 \).
We prove a more generalized form of the problem:
Let \( p \) be an odd prime and \( (a,p) = 1 \) and \( a \) be a quadratic residue modulo \( p \), then \( x^2 = a \) has a solution in \( \mathbb{Z}_p \).
Lemma1 Let \( F(x) \) be a polynomial with integer coefficient, then if \( F(x) \) is solvable in \( \mathbb{Z}/p^n \mathbb{Z} \) for all \( n \), then \( F(x) \) is solvable in \( \mathbb{Z}_p \).
Proof)
Let \( x_n \) be the solution to \( F(x) \) in \( \mathbb{Z}/p^n \mathbb{Z} \). If \( (x_n) \in \mathbb{Z}_p \) then we are done; however, it is not true in general. We will have to somehow obtain a \( p \)-adic integer from \( (x_n) \).
First observe that if \( n \geq m \), then \( x_n \equiv 0 ~\bmod{~p^m} \) because \( x_n \equiv 0 ~\bmod{~p^n} \). In particular, \( (x_n)_{n \geq m} \) has the property that \( x_n \equiv 0 ~\bmod{~p^m} \) for all \( n \). Considering \( (x_n) \) as a sequence in \( \mathbb{Z} \), we can always find a subsequence such that all its terms are congruent to \( 0 \) mod \( p^n \) for any \( n \) by deleting the first \( m-1 \) terms.
Because \( \mathbb{Z}/p \mathbb{Z} \) is finite, again considering \( (x_n) \) as a sequence, there exists \( y_1 \in \mathbb{Z}/p\mathbb{Z} \) such that \( x_n \equiv y_1 ~\bmod{~p} \) for infinitely many \( n \). We, then, have a subsequence \( (x_n^{(1)}) \) of \( (x_n) \) satisfies the following two properties,
1) \( x_n^{(1)} \equiv y_1 ~\bmod{~p} \)
2) \( F(x_n^{(1)}) \equiv 0 ~\bmod{~p} \)
In particular, \( F(y_1) \equiv F(x_n^{(1)}) \equiv 0 ~\bmod{~p} \).
Similarly, we take \( (x_n^{(2)}) \) a subsequence of \( (x_n^{(1)}) \) satisfying
1) \(x_n^{(2)} \equiv y_2 ~\bmod{~p^2} \)
2) \( F(x_n^{(2)}) \equiv 0 ~\bmod{~p^2} \)
where \( y_2 \in \mathbb{Z}/p^2 \mathbb{Z} \) which is equivalent to infinitely many terms in \( (x_n^{(1)}) \). The second can be easily obtained by removing the first term of \( (x_n^{(1)}) \) if necessary. Because \( x_n^{(2)} \) are terms in \( (x_n^{(1)}) \), \( x_n^{(2)} \equiv y_1 ~\bmod{~p} \), thus \( y_2 \equiv y_1 ~\bmod{~p} \). We again have \( F(y_2) \equiv 0 \) mod \( p^2 \). Continuing this process we obtain \( y_k \in \mathbb{Z}/p^k \mathbb{Z} \) such that
1) \(x_n^{(k)} \equiv y_k ~\bmod{~p^k} \)
2) \( F(x_n^{(k)}) \equiv 0 ~\bmod{~p^k} \)
with \( F(y_k) \equiv 0 ~\bmod{~p^k} \) and \( y_k \equiv y_{k-1} ~\bmod{~p^{k-1}} \). This means that \( y= (y_k) \in \mathbb{Z}_p \). Furthermore \( F(y_k) \equiv 0 ~\bmod{~p^k} \) is equivalent to saying that \( F(y) = 0 \) in \( \mathbb{Z}_p \).
Lemma2 Let \( p \) be an odd prime and \( (a,p) = 1 \). If \( a \) is a quadratic residue modulo \( p \), then \( a \) is a quadratic residue modulo \( p^n \) for any \( n \geq 1 \).
The converse is obviously true.
Proof) We assume that \( x^2 \equiv a ~\bmod{~p} \) for some \( x \). This proves the base case for induction. Now suppose that \( x^2 \equiv a ~\bmod{~p^n} \), then \( x^2 = a + p^nk \) for some \( k \). We consider an element of the form \( c= x + p^n l \). Then
\[
\begin{array}{lcl}
c^2 & = & x^2 + 2xp^nl + p^{2n}l^2 \\
& = & a + p^n(k+2xl) + 2^{2n}l^2 \\
& \equiv & a + p^n(k+2xl) ~\bmod{~p^{n+1}}
\end{array}
\]
The last equivalence follows from the fact that \( n > 1 \Rightarrow n^2 \leq 2n > n+1 \). If we can choose an appropriate \( l \) such that \( p | k+2xl \), then we are done. Suppose \( (x,p) \neq 1 \) which means that \( p | x \), then \( p | x^2 = a + p^nk \Rightarrow p |a \). This leads to a contradiction. Thus \( (x,p) = 1 \Rightarrow (2x, p^{n+1}) =1 \) as \( p \) is an odd prime. Thus we can let \( l \) be congruent to \( -k(2x)^{-1} \). Then \( c^2 \equiv a ~\bmod{~p^n} \) hence the result.
If we have a coprime quadratic residue \( a \) modulo an odd prime \( p \), then \( a \) is a quadratic residue modulo \( p^n \) for all \( n \) by Lemma 2. This is tantamount to saying that \( F(x) = x^2 - a \) has solution in \( \mathbb{Z}/p^n \mathbb{Z} \). By Lemma 1, \( F(x) \) has a solution in \( \mathbb{Z}_p \).
We prove a more generalized form of the problem:
Let \( p \) be an odd prime and \( (a,p) = 1 \) and \( a \) be a quadratic residue modulo \( p \), then \( x^2 = a \) has a solution in \( \mathbb{Z}_p \).
Lemma1 Let \( F(x) \) be a polynomial with integer coefficient, then if \( F(x) \) is solvable in \( \mathbb{Z}/p^n \mathbb{Z} \) for all \( n \), then \( F(x) \) is solvable in \( \mathbb{Z}_p \).
Proof)
Let \( x_n \) be the solution to \( F(x) \) in \( \mathbb{Z}/p^n \mathbb{Z} \). If \( (x_n) \in \mathbb{Z}_p \) then we are done; however, it is not true in general. We will have to somehow obtain a \( p \)-adic integer from \( (x_n) \).
First observe that if \( n \geq m \), then \( x_n \equiv 0 ~\bmod{~p^m} \) because \( x_n \equiv 0 ~\bmod{~p^n} \). In particular, \( (x_n)_{n \geq m} \) has the property that \( x_n \equiv 0 ~\bmod{~p^m} \) for all \( n \). Considering \( (x_n) \) as a sequence in \( \mathbb{Z} \), we can always find a subsequence such that all its terms are congruent to \( 0 \) mod \( p^n \) for any \( n \) by deleting the first \( m-1 \) terms.
Because \( \mathbb{Z}/p \mathbb{Z} \) is finite, again considering \( (x_n) \) as a sequence, there exists \( y_1 \in \mathbb{Z}/p\mathbb{Z} \) such that \( x_n \equiv y_1 ~\bmod{~p} \) for infinitely many \( n \). We, then, have a subsequence \( (x_n^{(1)}) \) of \( (x_n) \) satisfies the following two properties,
1) \( x_n^{(1)} \equiv y_1 ~\bmod{~p} \)
2) \( F(x_n^{(1)}) \equiv 0 ~\bmod{~p} \)
In particular, \( F(y_1) \equiv F(x_n^{(1)}) \equiv 0 ~\bmod{~p} \).
Similarly, we take \( (x_n^{(2)}) \) a subsequence of \( (x_n^{(1)}) \) satisfying
1) \(x_n^{(2)} \equiv y_2 ~\bmod{~p^2} \)
2) \( F(x_n^{(2)}) \equiv 0 ~\bmod{~p^2} \)
where \( y_2 \in \mathbb{Z}/p^2 \mathbb{Z} \) which is equivalent to infinitely many terms in \( (x_n^{(1)}) \). The second can be easily obtained by removing the first term of \( (x_n^{(1)}) \) if necessary. Because \( x_n^{(2)} \) are terms in \( (x_n^{(1)}) \), \( x_n^{(2)} \equiv y_1 ~\bmod{~p} \), thus \( y_2 \equiv y_1 ~\bmod{~p} \). We again have \( F(y_2) \equiv 0 \) mod \( p^2 \). Continuing this process we obtain \( y_k \in \mathbb{Z}/p^k \mathbb{Z} \) such that
1) \(x_n^{(k)} \equiv y_k ~\bmod{~p^k} \)
2) \( F(x_n^{(k)}) \equiv 0 ~\bmod{~p^k} \)
with \( F(y_k) \equiv 0 ~\bmod{~p^k} \) and \( y_k \equiv y_{k-1} ~\bmod{~p^{k-1}} \). This means that \( y= (y_k) \in \mathbb{Z}_p \). Furthermore \( F(y_k) \equiv 0 ~\bmod{~p^k} \) is equivalent to saying that \( F(y) = 0 \) in \( \mathbb{Z}_p \).
Lemma2 Let \( p \) be an odd prime and \( (a,p) = 1 \). If \( a \) is a quadratic residue modulo \( p \), then \( a \) is a quadratic residue modulo \( p^n \) for any \( n \geq 1 \).
The converse is obviously true.
Proof) We assume that \( x^2 \equiv a ~\bmod{~p} \) for some \( x \). This proves the base case for induction. Now suppose that \( x^2 \equiv a ~\bmod{~p^n} \), then \( x^2 = a + p^nk \) for some \( k \). We consider an element of the form \( c= x + p^n l \). Then
\[
\begin{array}{lcl}
c^2 & = & x^2 + 2xp^nl + p^{2n}l^2 \\
& = & a + p^n(k+2xl) + 2^{2n}l^2 \\
& \equiv & a + p^n(k+2xl) ~\bmod{~p^{n+1}}
\end{array}
\]
The last equivalence follows from the fact that \( n > 1 \Rightarrow n^2 \leq 2n > n+1 \). If we can choose an appropriate \( l \) such that \( p | k+2xl \), then we are done. Suppose \( (x,p) \neq 1 \) which means that \( p | x \), then \( p | x^2 = a + p^nk \Rightarrow p |a \). This leads to a contradiction. Thus \( (x,p) = 1 \Rightarrow (2x, p^{n+1}) =1 \) as \( p \) is an odd prime. Thus we can let \( l \) be congruent to \( -k(2x)^{-1} \). Then \( c^2 \equiv a ~\bmod{~p^n} \) hence the result.
Comments
Post a Comment